t = int(input())
u = 0
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    for k in range(len(a)):
        for j in range(1, len(a)):
            if (k + j) % 3 == 0 or (k + j) == 0:
                u += 1
            continue
    print(u)