Problem F

Perfect Square
Input: Standard Input

Output: Standard Output

 

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 nC3 triples 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 <10^18.

            -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                             Output for Sample Input

5

3

2 2 2

3

2 2 4

3

2 -2 2

3

0 2 5

4

10 14 35 29

 

3 0

1 1

1 0

2 1

0 1

 

Problem setter: Abdullah-al-Mahmud (Satej)

Special Thanks: Derek Kisman