def max_elements_divisible_by_3(arr):
    n = len(arr)
    total_sum = sum(arr)

    # If the total sum is already divisible by 3, all elements can be selected
    if total_sum % 3 == 0:
        return n

    # Calculate the remainders when dividing the total sum by 3
    remainder1 = total_sum % 3
    remainder2 = (total_sum * 2) % 3

    # Variables to store the count of elements with remainders 1 and 2
    count_remainder1 = count_remainder2 = 0

    # Iterate through the array and count the elements with remainders 1 and 2
    for num in arr:
        if num % 3 == remainder1:
            count_remainder1 += 1
        elif num % 3 == remainder2:
            count_remainder2 += 1

    # If the total sum has remainder 1 or 2, remove elements to make it divisible by 3
    if remainder1 == 1:
        return n - min(count_remainder1, 2)
    elif remainder2 == 1:
        return n - min(count_remainder2, 2)
    else:
        # If remainder is 0 or 2, remove elements to make it divisible by 3
        return n - min(count_remainder1, count_remainder2, 1)


# Input the number of test cases
T = int(input())

# Process each test case
for _ in range(T):
    # Input the size of the array
    N = int(input())

    # Input the elements of the array
    arr = list(map(int, input().split()))

    # Output the result for each test case
    result = max_elements_divisible_by_3(arr)
    print(result)


'''for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))

    count = 0

    new_arr = []
    for i in arr:
        if i % 3 == 0:
            count += 1
        else:
            new_arr.append(i)
    new_sum = sum(new_arr)

    if new_sum % 3 == 0:
        count += len(new_arr)
    elif new_sum % 3 == 1:
        if 1 in new_arr:
            count += (len(new_arr) - 1)
    elif new_sum % 3 == 2:
        if 2 in new_arr:
            count += (len(new_arr) - 1)
        elif new_arr.count(1) >= 2:
            count += (len(new_arr) - 2)

    print(count)'''