for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    
    summ = sum(l)
    if sum(l)%3 == 0:
        print(n)
    else:
        rem = summ%3
        if rem == 1:
            if 1 in l:
                l.remove(1)
                print(n - 1)
            elif 2 in l:
                l.remove(2)
                print(n - 1)
            else:
                print(0)
        
        elif rem == 2:
            if 2 in l:
                l.remove(2)
                print(n - 1)
            elif 1 in l:
                l.remove(1)
                print(n - 1)
            else:
                print(0)