# Perfect Square

People in the Byteland do not love large prime numbers. So they never use the integers having prime factors greater than 30. They love perfect square number. An integer is a perfect square if its square root is an integer. 0,1,4,9 are perfect square numbers. But -4 or 3 is not perfect square. Now people at Byteland have a sequence of n numbers. They select nC2 pairs of numbers from this sequence. A pair is a square pair if the product of its numbers is a perfect square. They are interested to calculate the number of square pairs X among these nC2 pairs. Again they select nC3triples of numbers from this sequence. A triple is a square triples if the product of its numbers is a perfect square. They are interested to calculate the number of square triples Y among these nC3 triples. Help them to calculate X and Y . Input First line of the input contains T the number of test case. Then following lines contains T Test cases. Each case starts with a line containing one integer n the length of the sequence. The next line contains n integers separated by a single space. Output For each test case output contain 2 integers X and Y separated by a single space. Constraints: • 0<n≤200000 • Each number in the sequence will have absolute value < 1018. • No number in the sequence will have prime factor greater than 30. But the sequence may contain the number zero as an exception. Sample Input 5 3 222 3 224 3 2 -2 2 3 025 4 10 14 35 29 Sample Output 30 11 10 21

2/2 01