t=int(input())
P=[]
u=0
for i in range(t):
    n=int(input())
    arr=list(map(int , input().split()))
    if n==len(arr):
        if sum(arr)%3==0 or sum(arr)==0:
            u = len(arr)
            print(u)
            u=0
        elif sum(arr)%3!=0:
            for m in arr:
                if m%3==0:
                    u+=1
                elif m%3 !=0:
                    P.append(m)
                    if sum(P)%3==1:
                        u += len(P)-1
                    elif sum(P)%3==2:
                        u +=len(P)-2
            print(u)
            u=0
            P=[]