t=int(input())
p=[]
u=0
for i in range(t):
    n=int(input())
    lst=list(map(int,input().split()))
    for z in range(n):
        p.append((lst[z]) % 3)
    if sum(lst) % 3 == 0 or sum(lst) == 0:
        u += len(lst)
        print(u)
        u = 0
    elif sum(lst) % 3 == 1:
        if 1 in p:
            u += len(lst) - 1
            print(u)
            u = 0
        elif 2 in p:
            u += len(lst) - 4
            if u>=0:
                print(u)
                u = 0
            
    elif sum(lst) % 3 == 2:
        if 2 in p:
            u += len(lst) - 1
            print(u)
            u = 0
        elif 1 in p:
            u += len(lst) - 2
            print(u)
            u = 0