### Cube Number

Time Limit: 2000 ms Memory Limit: 65536 KiB

#### Problem Description

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.

#### Input

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).

#### Output

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

#### Sample Input

1
5
1 2 3 4 9

#### Sample Output

2

#### Source

“浪潮杯”山东省第六届ACM大学生程序设计竞赛