 # Array based problem help .. please write code

You are given an array a consisting of n integers a1 , 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] 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≤t≤1000) — the number of queries.

The first line of each query contains one integer n

(1≤n≤100).

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

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.

SAMPLE INPUT

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

SAMPLE OUTPUT

3 3

Explanation

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]→[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]→[1,1,1,1,2,3]→[1,1,1,3,3]→[2,1,3,3]→[3,3,3].

1 Like

https://codeforces.com/contest/1176/problem/B
Read Tutorial of this problem and if still have problem, see submissions and understand them.

A classical problem.
Say, a=count of numbers in the array whose %3=0(perfectly divisible by 3)
b=count of numbers in the array whose %3=2
c=…same as above…%3=1 .
Lets not mess with the numbers which are already divisible by 3.
Now , numbers with x%3=2 and y%3=1, if you add them up, they become divisible by ‘3’ . Answer=min(b,c);
Now, say t=numbers still left=max(b,c)-min(b,c) . The numbers left are either all %3=2 or %3=1. If you combine 3 numbers of these type with each-other, they’ll be divisible by ‘3’,say rq=t/3.
Happy Coding 