L. Gamal's Final Riddle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sam07a, Omar, Abd-Elmohaymen had navigated countless perils in the Unknown. Now, at the very edge of the forest, blocking their path to freedom, stood Gamal. He wasn't just a chronicler; he was the enigmatic guardian of the Unknown's final secrets, and he would only allow them to pass if they could solve his ultimate riddle.

Gamal presented them with an array of $$$N$$$ peculiar leaves, each with an "essence value," $$$a_1,a_2, \cdots ,a_N$$$. To leave the Unknown, they had to count "Good Pairs" of these leaves.

A pair of leaves $$$(a_i,a_j)$$$ is a "Good Pair" if:

  1. $$$1 \le i \lt j \le N$$$,
  2. $$$\mathrm{lcm}(a_i, a_j)$$$ is a good number.

A number $$$x$$$ is considered good if, for every prime $$$p$$$ that divides $$$x$$$, $$$p^2$$$ also divides $$$x$$$.

Gamal's eyes gleamed. "Solve this, and the path is yours. Fail, and you shall forever remain a part of the Unknown!"

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of testcases.

For each testcase :

  • Single integer $$$N$$$ $$$(2 \leq N \leq 10^5)$$$ — the size of the array.

  • $$$N$$$ integers $$$a_1,a_2, \dots , a_n$$$ $$$(1 \leq a_i \leq 10^6)$$$

It is guaranteed that the sum of $$$N$$$ overall testcases does not exceed $$$2 \times 10^{5}$$$.

Output

Print a single integer — the number of pairs $$$(i, j)$$$ satisfying the conditions above.

Example
Input
1
5
10 18 29 36 20
Output
1