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)):
      if k % 3 == 0 or k == 0:
        u += 1
      for j in range(1, len(a)):
        if (k + j) % 3 == 0 or (k + j) == 0:
          u += 1
        continue
    print(u)