Time Limit: 1.0 s

Memory Limit: 64.0 MB

Description

Swadheen believes that number 3 has some magical properties. It is the first odd prime number,it is the integer part of pie, there exists 3 dimentions in real world and for many more reasons 3 is his most favourite number.
Recently, in his birthday his friend robi gifted him an array of n elements. As he likes number 3 so much his curious mind wants to know what is the maximum number of elements he can pick from the array so that the sum of those picked elements is divisible by 3 ??
can you help swadheen to solve this mystery ?
Note: 0 is also divisible by 3

Input

first line contains an integer T: number of test case
in each of the test case:
first line contains an integer N: number of elements of array
second line contains N integers : the elements of the array
1 <= T <= 100
1 <= N <= 10000
0 <= \(A_i\) <= 1000
sum of N over all test case will not exceed 10000

Output

for each testcase print a single integer: maximum number of elements

Sample

3
2
1 3
3
1 1 1
1
0

1
3
1