5311: I love triples
内存限制：128 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：2
解决：0
题目描述
Now Mr.I has an array a consisting of n integers.
He now wants to know how many triples (i,j,k) satisfy i<j<k and ai∗aj∗ak is a square number .
The definition of a square number is a number that can be expressed as the product of two identical integers.
For example, 1, 4, 9, 16, 25, and 36 are square numbers, but 2, 3, and 6 are not.
He now wants to know how many triples (i,j,k) satisfy i<j<k and ai∗aj∗ak is a square number .
The definition of a square number is a number that can be expressed as the product of two identical integers.
For example, 1, 4, 9, 16, 25, and 36 are square numbers, but 2, 3, and 6 are not.
输入
The first line contains an integer T(T≤6) . Then T test cases follow.
Each test case contains two lines.
The first one contains an integer n(1≤n≤105) — length of the array a.
The second one contains n integers a1,a2,...,an(1≤ai≤105)
Each test case contains two lines.
The first one contains an integer n(1≤n≤105) — length of the array a.
The second one contains n integers a1,a2,...,an(1≤ai≤105)
输出
For each test case, output a single line containing a single integer — the number of triples that meet the conditions.
样例输入 复制
1
6
1 2 4 8 16 32
样例输出 复制
10