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

    summ = sum(l)
    if summ % 3 == 0:
        print(n)
    else:
        rem = summ % 3
        reml = []
        if rem == 1:
            if 1 in l:
                reml.append(l.index(1))
            elif 2 in l:
                reml.append(l.index(2))
            else:
                print(0)
                continue
        elif rem == 2:
            if 2 in l:
                reml.append(l.index(2))
            elif 1 in l:
                reml.append(l.index(1))
            else:
                print(0)
                continue

        new = [x for i, x in enumerate(l) if i != reml[0]]
        print(len(new))