2553: Cube Number

In mathematics, a cube number is an integer that is the cube of an integer. In other words, it is the product of some integer with itself twice. For example, 27 is a cube number, since it can be written as 3 * 3 * 3.

Given an array of distinct integers (a1, a2, ..., an), you need to find the number of pairs (ai, aj) that satisfy (ai * aj) is a cube number.

The first line of the input contains an integer T (1 ≤ T ≤ 20) which means the number of test cases.

Then T lines follow, each line starts with a number N (1 ≤ N ≤ 100000), then N integers followed (all the integers are between 1 and 1000000).

For each test case, you should output the answer of each case.

1
5
1 2 3 4 9

2