B. Merge it!_given an array consisting of integers a1, a2,...,

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa consisting of nn integers a1,a2,…,ana1,a2,…,an.

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][2,1,4] you can obtain the following arrays: [3,4][3,4], [1,6][1,6] and [2,5][2,5].

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

You have to answer tt independent queries.

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of queries.

The first line of each query contains one integer nn (1≤n≤1001≤n≤100).

The second line of each query contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).

Output

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

Example

input

Copy

2
5
3 1 2 3 1
7
1 1 1 1 1 2 2

output

Copy

3
3

Note

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

In the second query you can obtain 33 elements divisible by 33 with the following sequence of operations: [1,1,1,1,1,2,2]→[1,1,1,1,2,3]→[1,1,1,3,3]→[2,1,3,3]→[3,3,3]

解题说明：此题是一道贪心题，将数列按被3除的余数分为三组，然后将余1组和余2组组合为3的倍数，然后将剩下的余1或余2组中的数字3个相加再次得到3的倍数，这样确保3的倍数的数字最多。

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
 
int main()
{
	int t, y, q, m;
	scanf("%d", &t);
	while (t--) 
	{
		scanf("%d", &y);
		int nt = 0, wq[5] = { 0 };
		while (y--) 
		{
			scanf("%d", &q);
			wq[q % 3]++;
		}
		nt = wq[0];
		m = min(wq[1], wq[2]);
		nt += m;
		wq[1] -= m;
		wq[2] -= m;
		nt += (wq[1] / 3 + wq[2] / 3);
		printf("%d\n", nt);
	}
	return 0;
}