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]$.
[{"code": "for i in range(int(input())):\n    n=int(input())\n    l1=list(map(int,input().split()))\n    type1=0\n    type2=0\n    ans=0\n    for item in l1:\n        if item%3==0:\n            ans+=1\n        elif item%3==1:\n            type1+=1\n        else :\n            type2+=1\n    x=min(type1,type2)\n    ans+=x\n    type1-=x\n    type2-=x\n    ans+=(type1//3+type2//3)\n    print(ans)", "passed": true, "time": 0.14, "memory": 14056.0, "status": "done"}, {"code": "#!/usr/bin/env python\nfor _ in range(int(input())):\n    n = int(input())\n    a = list(map(int, input().split()))\n    f = [0, 0, 0]\n    for ai in a:\n        f[ai % 3] += 1\n    m = min(f[1], f[2])\n    f[1] -= m; f[2] -= m\n    print(f[0] + m + (f[1] + f[2]) // 3)\n", "passed": true, "time": 0.18, "memory": 14224.0, "status": "done"}, {"code": "#JMD\n#Nagendra Jha-4096\n\n \nimport sys\nimport math\n\n#import fractions\n#import numpy\n \n###File Operations###\nfileoperation=0\nif(fileoperation):\n    orig_stdout = sys.stdout\n    orig_stdin = sys.stdin\n    inputfile = open('W:/Competitive Programming/input.txt', 'r')\n    outputfile = open('W:/Competitive Programming/output.txt', 'w')\n    sys.stdin = inputfile\n    sys.stdout = outputfile\n\n###Defines...###\nmod=1000000007\n \n###FUF's...###\ndef nospace(l):\n    ans=''.join(str(i) for i in l)\n    return ans\n \n \n \n##### Main ####\nt=int(input())\nfor tt in range(t):\n    n=int(input())\n    #n,k,s= map(int, sys.stdin.readline().split(' '))\n    a=list(map(int,sys.stdin.readline().split(' ')))\n    z=0\n    o=0\n    two=0\n    for nu in a:\n        if(nu%3==0):\n            z+=1\n        elif(nu%3==1):\n            o+=1\n        else:\n            two+=1\n    ans=min(o,two)\n    o-=ans\n    two-=ans\n    if(o):\n        ans+=o//3\n    if two:\n        ans+=two//3\n    print(ans+z)\n\n    \n    \n#####File Operations#####\nif(fileoperation):\n    sys.stdout = orig_stdout\n    sys.stdin = orig_stdin\n    inputfile.close()\n    outputfile.close()", "passed": true, "time": 0.14, "memory": 14292.0, "status": "done"}, {"code": "\n\nfor _ in range(int(input())):\n\tn=int(input())\n\ta=list(map(int,input().split(\" \")))\n\n\tfor i in range(n):\n\t\ta[i]%=3\n\n\tc0=0\n\tc1=0\n\tc2=0\n\n\tfor i in a:\n\t\tif(i==0):\n\t\t\tc0+=1\n\t\telif(i==1):\n\t\t\tc1+=1\n\t\telse:\n\t\t\tc2+=1\n\n\tans=0\n\n\tans+=c0\n\n\tnow=min(c2,c1)\n\n\tans+=now\n\n\tc1-=now\n\tc2-=now\n\n\tans+=c1//3\n\tans+=c2//3\n\n\tprint(ans)\n", "passed": true, "time": 0.24, "memory": 14396.0, "status": "done"}, {"code": "t = int(input())\nfor i in range(t):\n    n = int(input())\n    a = list(map(int, input().split()))\n    d = [0] * 3\n    for j in range(n):\n        d[a[j] % 3] += 1\n\n    num = 0\n    num += d[0]\n    k = min(d[1], d[2])\n    num += k\n    d[1], d[2] = d[1] - k, d[2] - k\n    num += d[1] // 3\n    num += d[2] // 3\n    print(num)", "passed": true, "time": 0.15, "memory": 14264.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n    n = int(input())\n    a = list(map(int, input().split()))\n    c = [0, 0, 0]\n    for i in a:\n        c[i % 3] += 1\n    if c[1] >= c[2]:\n        print(c[0] + c[2] + (c[1] - c[2]) // 3)\n    else:\n        print(c[0] + c[1] + (c[2] - c[1]) // 3)\n", "passed": true, "time": 0.18, "memory": 14120.0, "status": "done"}, {"code": "def ain():\n    return map(int,input().split())\ndef lin():\n    return list(ain())\n\n\ndef plist(l):\n    for x in l:\n        print(x, end= ' ')\n    print()\n\ndef indexof(l,v,l3):\n    return l3[v]\n\n\nfor _ in range(int(input())):\n    n = int(input())\n    l = lin()\n    a=0\n    b=0\n    c=0\n    for x in l:\n        if x%3 == 0:\n            a+=1\n        elif x%3 == 1:\n            b+=1\n        else:\n            c += 1\n    s = a + min(b,c)\n    if b > c:\n        s += (b-c)//3\n    else:\n        s += (c-b)//3\n\n    print(s)", "passed": true, "time": 0.23, "memory": 14328.0, "status": "done"}, {"code": "t = int(input())\nfor l in range(t):\n    n = int(input())\n    arr = list(map(int,input().split()))\n    co1 = 0\n    co2 = 0\n    co = 0\n    for i in arr:\n        if i%3==0:\n            co += 1\n        if i%3==1:\n            co1 += 1\n        if i%3==2:\n            co2 += 1\n    ans = co\n    ans += min(co1,co2)\n    left = max(co2,co1)-min(co2,co1)\n    ans += int(left/3)\n    print(ans)", "passed": true, "time": 0.17, "memory": 14104.0, "status": "done"}, {"code": "def main():\n    for i in range(int(input())):\n        n = int(input())\n        a = [int(i) for i in input().split()]\n        thr = 0\n        tw = 0\n        on = 0\n        for val in a:\n            if val % 3 == 0:\n                thr += 1\n            elif val % 3 == 2:\n                tw += 1\n            else:\n                on += 1\n        if tw == on:\n            print(thr + tw)\n        elif tw > on:\n            print(thr + on + (tw - on) // 3)\n        else:\n            print(thr + tw + (on - tw) // 3)\n\n\nmain()\n", "passed": true, "time": 0.15, "memory": 14244.0, "status": "done"}, {"code": "def solve():\n    n = int(input())\n    a = list(map(int, input().split()))\n    p0, p1, p2 = 0, 0, 0\n    for el in a:\n        if el % 3 == 0:\n            p0 += 1\n        elif el % 3 == 1:\n            p1 += 1\n        else:\n            p2 += 1\n    return p0 + min(p1, p2) + (max(p1, p2) - min(p1, p2)) // 3\n\nq = int(input())\nfor i in range(q):\n    print(solve())", "passed": true, "time": 0.17, "memory": 14308.0, "status": "done"}, {"code": "import math\nimport bisect\nimport heapq\nfrom collections import defaultdict\n\n\ndef egcd(a, b):\n    if a == 0:\n        return (b, 0, 1)\n    else:\n        g, x, y = egcd(b % a, a)\n        return (g, y - (b // a) * x, x)\n\n\ndef mulinv(b, n):\n    g, x, _ = egcd(b, n)\n    if g == 1:\n        return x % n\n\n\ndef isprime(n):\n    for d in range(2, int(math.sqrt(n))+1):\n        if n % d == 0:\n            return False\n    return True\n\n\ndef argsort(ls):\n    return sorted(range(len(ls)), key=ls.__getitem__)\n\n\ndef f(p=0):\n    if p == 1:\n        return map(int, input().split())\n    elif p == 2:\n        return list(map(int, input().split()))\n    elif p == 3:\n        return list(input())\n    else:\n        return int(input())\n\n\nclass DisjointSet:\n    _disjoint_set = list()\n\n    def __init__(self, init_arr):\n        self._disjoint_set = []\n        if init_arr:\n            for item in list(set(init_arr)):\n                self._disjoint_set.append([item])\n\n    def _find_index(self, elem):\n        for item in self._disjoint_set:\n            if elem in item:\n                return self._disjoint_set.index(item)\n        return None\n\n    def find(self, elem):\n        for item in self._disjoint_set:\n            if elem in item:\n                return self._disjoint_set[self._disjoint_set.index(item)]\n        return None\n\n    def union(self, elem1, elem2):\n        index_elem1 = self._find_index(elem1)\n        index_elem2 = self._find_index(elem2)\n        if index_elem1 != index_elem2 and index_elem1 is not None and index_elem2 is not None:\n            self._disjoint_set[index_elem2] = self._disjoint_set[index_elem2] + self._disjoint_set[index_elem1]\n            del self._disjoint_set[index_elem1]\n        return self._disjoint_set\n\n    def get(self):\n        return self._disjoint_set\n\n\ndef graph(n, m, edg=False):\n    edges = []\n    visited = [0]*n\n    g = [list() for _ in range(n+1)]\n    for i in range(m):\n        u, v = f(1)\n        g[u].append(v)\n        g[v].append(u)\n        if edg:\n            edges.append((u, v))\n\n    if edg:\n        return g, visited, edg\n    else:\n        return g, visited\n\n\ndef bfs(g, visited):\n    queue = [1]\n    visited[1] = 1\n    for u in queue:\n        for v in g[u]:\n            if visited[v] == 0:\n                queue.append(v)\n            visited[v] = 1\n\n\ndef dfs(u, g, visited):\n    print(u)\n    visited[u] = 1\n    for v in g[u]:\n        if visited[v] == 0:\n            dfs(v, g, visited)\n\n\nt = f()\nfor i in range(t):\n    n = f()\n    cl = f(2)\n    count = 0\n    a = 0\n    b = 0\n    for i in range(n):\n        if cl[i]%3==0:\n            count+=1\n        elif cl[i]%3==1:\n            a+=1\n        else:\n            b+=1\n\n    print(count+min(a, b)+(max(a, b) - min(a, b))//3)", "passed": true, "time": 0.15, "memory": 14532.0, "status": "done"}, {"code": "q = int(input())\nfor _ in range(q):\n    n = int(input())\n    u = list(map(int, input().split()))\n    a0, a1, a2 = [0, 0, 0]\n    for i in range(n):\n        if u[i] % 3 == 0:\n            a0 += 1\n        elif u[i] % 3 == 1:\n            a1 += 1\n        else:\n            a2 += 1\n    w1 = a0 + min(a1, a2)\n    w2 = min(a1, a2)\n    a1 -= w2; a2 -= w2\n    w1 += a1 // 3 + a2 // 3\n    print(w1)\n    \n", "passed": true, "time": 0.14, "memory": 14132.0, "status": "done"}, {"code": "n = int(input())\nfor i in range(n):\n    q = int(input())\n    l = list(map(int, input().split()))\n    a = 0\n    b = 0\n    c = 0\n    for i in range(q):\n        if(l[i]%3==0):\n            a+=1\n        elif(l[i]%3==1):\n            b+=1\n        else:\n            c+=1\n    print(a+min(c,b)+(max(c,b)-min(c,b))//3)\n", "passed": true, "time": 0.24, "memory": 14196.0, "status": "done"}, {"code": "def f():\n    l=[int(k)%3 for k in input().split()]\n    a=sum([k==1 for k in l])\n    b=sum([k==2 for k in l])\n    a,b=sorted((a,b))\n    c=len(l)-a-b\n    return (a+c+(b-a)//3)\nfor k in range(int(input())):\n    input()\n    print(f())\n", "passed": true, "time": 0.14, "memory": 14096.0, "status": "done"}, {"code": "from collections import Counter\n\nt=int(input())\nfor query in range(t):\n    n=int(input())\n    A=list(map(int,input().split()))\n\n    B=[i%3 for i in A]\n\n    C=Counter(B)\n\n    ANS=C[0]\n    x=min(C[1],C[2])\n    ANS+=x\n    C[1]-=x\n    C[2]-=x\n\n    ANS+=C[1]//3+C[2]//3\n\n    print(ANS)\n\n    \n", "passed": true, "time": 0.14, "memory": 14348.0, "status": "done"}, {"code": "for i in range(int(input())):\n    n = int(input()) \n    A = list(map(int, input().split())) \n    d = {0:0,1:0, 2:0} \n    for i in A:\n        d[i % 3] += 1\n    Z = min(d[1],d[2])\n    d[1] -= Z\n    d[2] -= Z\n    print(d[0] + Z + d[1] // 3 + d[2] // 3)\n            \n", "passed": true, "time": 0.14, "memory": 14200.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n    n = int(input())\n    a = list(map(int, input().split()))\n    a = [i % 3 for i in a]\n    c0 = a.count(0)\n    c1 = a.count(1)\n    c2 = a.count(2)\n    x = min(c1, c2)\n    c1 -= x\n    c2 -= x\n    s = c0 + x + c1 // 3 + c2 // 3\n    print(s)\n", "passed": true, "time": 0.15, "memory": 14232.0, "status": "done"}, {"code": "from sys import stdin\nq=int(stdin.readline().strip())\nfor i in range(q):\n    n=int(stdin.readline().strip())\n    s=list(map(int,stdin.readline().strip().split()))\n    u=0\n    z=0\n    d=0\n    for i in range(n):\n        s[i]=s[i]%3\n        if s[i]==0:\n            z+=1\n        elif s[i]==1:\n            u+=1\n        else:\n            d+=1\n    ans=0\n    ans+=z\n    ans+=min(u,d)\n    if u<=d:\n        d-=u\n        x=0\n        for i in range(d):\n            x+=2\n            x=x%3\n            if x==0:\n                ans+=1\n    else:\n        u-=d\n        x=0\n        for i in range(u):\n            x+=1\n            x=x%3\n            if x==0:\n                ans+=1\n    print(ans)\n            \n", "passed": true, "time": 0.14, "memory": 14328.0, "status": "done"}, {"code": "n = int(input())\nfor i in range(n):\n    x = int(input())\n    a = [int(i) for i in input().split()]\n    zero = 0\n    one = 0\n    two = 0\n    for i in range(x):\n        if a[i] % 3 == 0:\n            zero += 1\n        elif a[i] % 3 == 1:\n            one += 1\n        else:\n            two += 1\n    print(zero + min(two, one) + (max(two, one) - min(two, one)) // 3)", "passed": true, "time": 0.14, "memory": 14252.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n    n = int(input())\n    l = list(map(int, input().split()))\n    cnt1 = 0\n    cnt0 = 0\n    cnt2 = 0\n    for j in range(n):\n        if l[j] % 3 == 0:\n            cnt0 += 1\n        elif l[j] % 3 == 1:\n            cnt1 += 1\n        else:\n            cnt2 += 1\n    cnt0 += min(cnt2, cnt1)\n    tmp = cnt2\n    cnt2 -= min(tmp, cnt1)\n    cnt1 -= min(tmp, cnt1)\n    print(cnt0 + cnt2 // 3 + cnt1 // 3)", "passed": true, "time": 0.14, "memory": 14056.0, "status": "done"}, {"code": "from collections import Counter as C\nfor TT in range(1, int(input()) + 1):\n    n = int(input())   \n    c = C(map(lambda x: int(x) % 3, input().split()))\n    x, y, z = c.get(0, 0), c.get(1, 0), c.get(2, 0) \n    d = min(y, z)\n    y -= d\n    z -= d\n    x += d\n    y //= 3\n    z //= 3\n    print(x + y + z)", "passed": true, "time": 0.14, "memory": 14056.0, "status": "done"}, {"code": "t = int(input())\nfor i in range(t):\n    n = int(input())\n    a = [int(s) for s in input().split(' ')]\n    ost0, ost1, ost2 = 0, 0, 0\n    col = 0\n    for el in a:\n        if el % 3 == 0:\n            ost0 += 1\n        elif el % 3 == 1:\n            ost1 += 1\n        elif el % 3 == 2:\n            ost2 += 1\n    col += ost0 + min(ost1, ost2) + (max(ost1, ost2) - min(ost1, ost2)) // 3\n    print(col)", "passed": true, "time": 0.14, "memory": 14192.0, "status": "done"}, {"code": "t = int(input())\n\nfor _ in range(t):\n    n = int(input())\n    arr = list(map(int, input().split()))\n\n    mod_0, mod_1, mod_2 = 0, 0, 0\n    for el in arr:\n        if el % 3 == 0:\n            mod_0 += 1\n        elif el % 3 == 1:\n            mod_1 += 1\n        elif el % 3 == 2:\n            mod_2 += 1\n\n    res = mod_0\n\n    # add mod 1 and mod 2\n    min_1_2 = min(mod_1, mod_2)\n    res += min_1_2\n    mod_1 -= min_1_2\n    mod_2 -= min_1_2\n\n    # add mod 1, 2\n    res += mod_1 // 3\n    res += mod_2 // 3\n    print(res)\n", "passed": true, "time": 0.14, "memory": 14280.0, "status": "done"}, {"code": "t = int(input())\n\ndef solve(arr, n):\n    ones = 0\n    twos = 0\n    for item in arr:\n        if item % 3 == 1:\n            ones += 1\n        elif item % 3 == 2:\n            twos += 1\n    zeros = n - ones - twos\n    threes = abs(ones - twos) // 3\n    return zeros + min(ones, twos) + threes\n\nfor _ in range(t):\n    n = int(input())\n    arr = list(map(int, input().strip().split()))\n    print(solve(arr, n))\n", "passed": true, "time": 0.14, "memory": 14320.0, "status": "done"}, {"code": "q = int(input())\nfor iqwwq in range(q):\n    n = int(input())\n    sp = input().split()\n    k0, k1, k2 = 0, 0, 0\n    for i in sp:\n        if int(i) % 3 == 0:\n            k0 += 1\n        elif int(i) % 3 == 1:\n            k1 += 1\n        else:\n            k2 += 1\n    if k2 > k1:\n        k2 -= k1\n        print(k0 + k1 + (k2 // 3))\n    else:\n        k1 -= k2\n        print(k0 + (k1 // 3) + k2)", "passed": true, "time": 0.14, "memory": 14112.0, "status": "done"}]