2553: Cube Number
内存限制:128 MB
时间限制:3.000 S
评测方式:文本比较
命题人:
提交:20
解决:4
题目描述
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