There was a power value associated with each soldier of Ram’s troop. It was a known belief that if two soldiers could be paired such that their total power can be divided by 3 perfectly, the pairing becomes ultra-powerful. Ram was curious as to see how many such pairings were possible.
Help Ram find out the number of pairings(not necessarily unique) possible from his troop.

INPUT:
An integer T (1 ≤ T ≤ 1000) : number of testcases
Each test case is represented by a number N(1 ≤ N ≤ 100) denoting the number of soldiers followed by an unordered list of N values representing the soldier’s power P(1 ≤ P ≤ 10000).

OUTPUT:
For each test case T, output the value of number of possible pairs from the given list such that the sum of the values in each pair is a multiple of 3.

SAMPLE INPUT
3
5
3 6 7 2 9
4
2 1 3 4
3
9 9 9

SAMPLE OUTPUT
4
2
3

Explanation

In the first test case, the groups are (3,6),(3,9),(9,6),(7,2).

In the second test case, the groups are (2,1),(2,4)

In the third test case, the groups are (9,9),(9,9),(9,9))

见题面

见题面