K. Math Madness
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, please count the number of pairs of indices $$$(i, j)$$$ such that $$$1 \leq i \leq j \leq n$$$ and $$$\frac{\mathop{\mathrm{lcm}}(a_i, a_j)}{\mathop{\mathrm{gcd}}(a_i, a_j)}$$$ is divisible by $$$\max(a_i, a_j)$$$.

Here, $$$\mathop{\mathrm{lcm}}(x, y)$$$ denotes the least common multiple of $$$x$$$ and $$$y$$$, and $$$\mathop{\mathrm{gcd}}(x, y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$.

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10 \cdot n$$$).

It is guaranteed that the sum of $$$n$$$ over all the test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer — the number of pairs of indices that satisfy the condition.

Example
Input
4
3
2 3 3
5
2 3 2 2 7
3
3 3 3
6
2 10 23 12 10 40
Output
2
7
0
5