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