You are given an array $a$ consisting of $n$ integers $a_1, a_2, \dots , a_n$.

In one operation you can choose two elements of the array and replace them with the element equal to their sum (it does not matter where you insert the new element). For example, from the array $[2, 1, 4]$ you can obtain the following arrays: $[3, 4]$, $[1, 6]$ and $[2, 5]$.

Your task is to find the maximum possible number of elements divisible by $3$ that are in the array after performing this operation an arbitrary (possibly, zero) number of times.

You have to answer $t$ independent queries.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of queries.

The first line of each query contains one integer $n$ ($1 \le n \le 100$).

The second line of each query contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le 10^9$). 


-----Output-----

For each query print one integer in a single line — the maximum possible number of elements divisible by $3$ that are in the array after performing described operation an arbitrary (possibly, zero) number of times.


-----Example-----
Input
2
5
3 1 2 3 1
7
1 1 1 1 1 2 2

Output
3
3



-----Note-----

In the first query of the example you can apply the following sequence of operations to obtain $3$ elements divisible by $3$: $[3, 1, 2, 3, 1] \rightarrow [3, 3, 3, 1]$.

In the second query you can obtain $3$ elements divisible by $3$ with the following sequence of operations: $[1, 1, 1, 1, 1, 2, 2] \rightarrow [1, 1, 1, 1, 2, 3] \rightarrow [1, 1, 1, 3, 3] \rightarrow [2, 1, 3, 3] \rightarrow [3, 3, 3]$.

Difficulty: introductory

Starter code:

Solutions:
for i in range(int(input())):
    n=int(input())
    l1=list(map(int,input().split()))
    type1=0
    type2=0
    ans=0
    for item in l1:
        if item%3==0:
            ans+=1
        elif item%3==1:
            type1+=1
        else :
            type2+=1
    x=min(type1,type2)
    ans+=x
    type1-=x
    type2-=x
    ans+=(type1//3+type2//3)
    print(ans)

#!/usr/bin/env python
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    f = [0, 0, 0]
    for ai in a:
        f[ai % 3] += 1
    m = min(f[1], f[2])
    f[1] -= m; f[2] -= m
    print(f[0] + m + (f[1] + f[2]) // 3)


#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
 
##### Main ####
t=int(input())
for tt in range(t):
    n=int(input())
    #n,k,s= map(int, sys.stdin.readline().split(' '))
    a=list(map(int,sys.stdin.readline().split(' ')))
    z=0
    o=0
    two=0
    for nu in a:
        if(nu%3==0):
            z+=1
        elif(nu%3==1):
            o+=1
        else:
            two+=1
    ans=min(o,two)
    o-=ans
    two-=ans
    if(o):
        ans+=o//3
    if two:
        ans+=two//3
    print(ans+z)

    
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()



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

	for i in range(n):
		a[i]%=3

	c0=0
	c1=0
	c2=0

	for i in a:
		if(i==0):
			c0+=1
		elif(i==1):
			c1+=1
		else:
			c2+=1

	ans=0

	ans+=c0

	now=min(c2,c1)

	ans+=now

	c1-=now
	c2-=now

	ans+=c1//3
	ans+=c2//3

	print(ans)


t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    d = [0] * 3
    for j in range(n):
        d[a[j] % 3] += 1

    num = 0
    num += d[0]
    k = min(d[1], d[2])
    num += k
    d[1], d[2] = d[1] - k, d[2] - k
    num += d[1] // 3
    num += d[2] // 3
    print(num)

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    c = [0, 0, 0]
    for i in a:
        c[i % 3] += 1
    if c[1] >= c[2]:
        print(c[0] + c[2] + (c[1] - c[2]) // 3)
    else:
        print(c[0] + c[1] + (c[2] - c[1]) // 3)


def ain():
    return map(int,input().split())
def lin():
    return list(ain())


def plist(l):
    for x in l:
        print(x, end= ' ')
    print()

def indexof(l,v,l3):
    return l3[v]


for _ in range(int(input())):
    n = int(input())
    l = lin()
    a=0
    b=0
    c=0
    for x in l:
        if x%3 == 0:
            a+=1
        elif x%3 == 1:
            b+=1
        else:
            c += 1
    s = a + min(b,c)
    if b > c:
        s += (b-c)//3
    else:
        s += (c-b)//3

    print(s)

t = int(input())
for l in range(t):
    n = int(input())
    arr = list(map(int,input().split()))
    co1 = 0
    co2 = 0
    co = 0
    for i in arr:
        if i%3==0:
            co += 1
        if i%3==1:
            co1 += 1
        if i%3==2:
            co2 += 1
    ans = co
    ans += min(co1,co2)
    left = max(co2,co1)-min(co2,co1)
    ans += int(left/3)
    print(ans)

def main():
    for i in range(int(input())):
        n = int(input())
        a = [int(i) for i in input().split()]
        thr = 0
        tw = 0
        on = 0
        for val in a:
            if val % 3 == 0:
                thr += 1
            elif val % 3 == 2:
                tw += 1
            else:
                on += 1
        if tw == on:
            print(thr + tw)
        elif tw > on:
            print(thr + on + (tw - on) // 3)
        else:
            print(thr + tw + (on - tw) // 3)


main()


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    p0, p1, p2 = 0, 0, 0
    for el in a:
        if el % 3 == 0:
            p0 += 1
        elif el % 3 == 1:
            p1 += 1
        else:
            p2 += 1
    return p0 + min(p1, p2) + (max(p1, p2) - min(p1, p2)) // 3

q = int(input())
for i in range(q):
    print(solve())

import math
import bisect
import heapq
from collections import defaultdict


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)


def mulinv(b, n):
    g, x, _ = egcd(b, n)
    if g == 1:
        return x % n


def isprime(n):
    for d in range(2, int(math.sqrt(n))+1):
        if n % d == 0:
            return False
    return True


def argsort(ls):
    return sorted(range(len(ls)), key=ls.__getitem__)


def f(p=0):
    if p == 1:
        return map(int, input().split())
    elif p == 2:
        return list(map(int, input().split()))
    elif p == 3:
        return list(input())
    else:
        return int(input())


class DisjointSet:
    _disjoint_set = list()

    def __init__(self, init_arr):
        self._disjoint_set = []
        if init_arr:
            for item in list(set(init_arr)):
                self._disjoint_set.append([item])

    def _find_index(self, elem):
        for item in self._disjoint_set:
            if elem in item:
                return self._disjoint_set.index(item)
        return None

    def find(self, elem):
        for item in self._disjoint_set:
            if elem in item:
                return self._disjoint_set[self._disjoint_set.index(item)]
        return None

    def union(self, elem1, elem2):
        index_elem1 = self._find_index(elem1)
        index_elem2 = self._find_index(elem2)
        if index_elem1 != index_elem2 and index_elem1 is not None and index_elem2 is not None:
            self._disjoint_set[index_elem2] = self._disjoint_set[index_elem2] + self._disjoint_set[index_elem1]
            del self._disjoint_set[index_elem1]
        return self._disjoint_set

    def get(self):
        return self._disjoint_set


def graph(n, m, edg=False):
    edges = []
    visited = [0]*n
    g = [list() for _ in range(n+1)]
    for i in range(m):
        u, v = f(1)
        g[u].append(v)
        g[v].append(u)
        if edg:
            edges.append((u, v))

    if edg:
        return g, visited, edg
    else:
        return g, visited


def bfs(g, visited):
    queue = [1]
    visited[1] = 1
    for u in queue:
        for v in g[u]:
            if visited[v] == 0:
                queue.append(v)
            visited[v] = 1


def dfs(u, g, visited):
    print(u)
    visited[u] = 1
    for v in g[u]:
        if visited[v] == 0:
            dfs(v, g, visited)


t = f()
for i in range(t):
    n = f()
    cl = f(2)
    count = 0
    a = 0
    b = 0
    for i in range(n):
        if cl[i]%3==0:
            count+=1
        elif cl[i]%3==1:
            a+=1
        else:
            b+=1

    print(count+min(a, b)+(max(a, b) - min(a, b))//3)

q = int(input())
for _ in range(q):
    n = int(input())
    u = list(map(int, input().split()))
    a0, a1, a2 = [0, 0, 0]
    for i in range(n):
        if u[i] % 3 == 0:
            a0 += 1
        elif u[i] % 3 == 1:
            a1 += 1
        else:
            a2 += 1
    w1 = a0 + min(a1, a2)
    w2 = min(a1, a2)
    a1 -= w2; a2 -= w2
    w1 += a1 // 3 + a2 // 3
    print(w1)
    


n = int(input())
for i in range(n):
    q = int(input())
    l = list(map(int, input().split()))
    a = 0
    b = 0
    c = 0
    for i in range(q):
        if(l[i]%3==0):
            a+=1
        elif(l[i]%3==1):
            b+=1
        else:
            c+=1
    print(a+min(c,b)+(max(c,b)-min(c,b))//3)


def f():
    l=[int(k)%3 for k in input().split()]
    a=sum([k==1 for k in l])
    b=sum([k==2 for k in l])
    a,b=sorted((a,b))
    c=len(l)-a-b
    return (a+c+(b-a)//3)
for k in range(int(input())):
    input()
    print(f())


from collections import Counter

t=int(input())
for query in range(t):
    n=int(input())
    A=list(map(int,input().split()))

    B=[i%3 for i in A]

    C=Counter(B)

    ANS=C[0]
    x=min(C[1],C[2])
    ANS+=x
    C[1]-=x
    C[2]-=x

    ANS+=C[1]//3+C[2]//3

    print(ANS)

    


for i in range(int(input())):
    n = int(input()) 
    A = list(map(int, input().split())) 
    d = {0:0,1:0, 2:0} 
    for i in A:
        d[i % 3] += 1
    Z = min(d[1],d[2])
    d[1] -= Z
    d[2] -= Z
    print(d[0] + Z + d[1] // 3 + d[2] // 3)
            


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a = [i % 3 for i in a]
    c0 = a.count(0)
    c1 = a.count(1)
    c2 = a.count(2)
    x = min(c1, c2)
    c1 -= x
    c2 -= x
    s = c0 + x + c1 // 3 + c2 // 3
    print(s)


from sys import stdin
q=int(stdin.readline().strip())
for i in range(q):
    n=int(stdin.readline().strip())
    s=list(map(int,stdin.readline().strip().split()))
    u=0
    z=0
    d=0
    for i in range(n):
        s[i]=s[i]%3
        if s[i]==0:
            z+=1
        elif s[i]==1:
            u+=1
        else:
            d+=1
    ans=0
    ans+=z
    ans+=min(u,d)
    if u<=d:
        d-=u
        x=0
        for i in range(d):
            x+=2
            x=x%3
            if x==0:
                ans+=1
    else:
        u-=d
        x=0
        for i in range(u):
            x+=1
            x=x%3
            if x==0:
                ans+=1
    print(ans)
            


n = int(input())
for i in range(n):
    x = int(input())
    a = [int(i) for i in input().split()]
    zero = 0
    one = 0
    two = 0
    for i in range(x):
        if a[i] % 3 == 0:
            zero += 1
        elif a[i] % 3 == 1:
            one += 1
        else:
            two += 1
    print(zero + min(two, one) + (max(two, one) - min(two, one)) // 3)

q = int(input())
for i in range(q):
    n = int(input())
    l = list(map(int, input().split()))
    cnt1 = 0
    cnt0 = 0
    cnt2 = 0
    for j in range(n):
        if l[j] % 3 == 0:
            cnt0 += 1
        elif l[j] % 3 == 1:
            cnt1 += 1
        else:
            cnt2 += 1
    cnt0 += min(cnt2, cnt1)
    tmp = cnt2
    cnt2 -= min(tmp, cnt1)
    cnt1 -= min(tmp, cnt1)
    print(cnt0 + cnt2 // 3 + cnt1 // 3)

from collections import Counter as C
for TT in range(1, int(input()) + 1):
    n = int(input())   
    c = C(map(lambda x: int(x) % 3, input().split()))
    x, y, z = c.get(0, 0), c.get(1, 0), c.get(2, 0) 
    d = min(y, z)
    y -= d
    z -= d
    x += d
    y //= 3
    z //= 3
    print(x + y + z)

t = int(input())
for i in range(t):
    n = int(input())
    a = [int(s) for s in input().split(' ')]
    ost0, ost1, ost2 = 0, 0, 0
    col = 0
    for el in a:
        if el % 3 == 0:
            ost0 += 1
        elif el % 3 == 1:
            ost1 += 1
        elif el % 3 == 2:
            ost2 += 1
    col += ost0 + min(ost1, ost2) + (max(ost1, ost2) - min(ost1, ost2)) // 3
    print(col)

t = int(input())

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

    mod_0, mod_1, mod_2 = 0, 0, 0
    for el in arr:
        if el % 3 == 0:
            mod_0 += 1
        elif el % 3 == 1:
            mod_1 += 1
        elif el % 3 == 2:
            mod_2 += 1

    res = mod_0

    # add mod 1 and mod 2
    min_1_2 = min(mod_1, mod_2)
    res += min_1_2
    mod_1 -= min_1_2
    mod_2 -= min_1_2

    # add mod 1, 2
    res += mod_1 // 3
    res += mod_2 // 3
    print(res)


t = int(input())

def solve(arr, n):
    ones = 0
    twos = 0
    for item in arr:
        if item % 3 == 1:
            ones += 1
        elif item % 3 == 2:
            twos += 1
    zeros = n - ones - twos
    threes = abs(ones - twos) // 3
    return zeros + min(ones, twos) + threes

for _ in range(t):
    n = int(input())
    arr = list(map(int, input().strip().split()))
    print(solve(arr, n))


q = int(input())
for iqwwq in range(q):
    n = int(input())
    sp = input().split()
    k0, k1, k2 = 0, 0, 0
    for i in sp:
        if int(i) % 3 == 0:
            k0 += 1
        elif int(i) % 3 == 1:
            k1 += 1
        else:
            k2 += 1
    if k2 > k1:
        k2 -= k1
        print(k0 + k1 + (k2 // 3))
    else:
        k1 -= k2
        print(k0 + (k1 // 3) + k2)