OnlineJudge 3 现已推出。点此体验新版：Square Number | SDUT OnlineJudge

### Square Number

Time Limit: 1000 ms
Memory Limit: 65536 KiB

#### Problem Description

In mathematics, a square number is an integer that is the square of an integer. In other words, it is the product of some integer with itself. For example, 9 is a square number, since it can be written as 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 square 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 12

#### Sample Output

2

#### Hint

#### Source

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