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.
-
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))
