You are given an array of integers $a_1, a_2, \ldots, a_n$.

A pair of integers $(i, j)$, such that $1 \le i < j \le n$, is called good, if there does not exist an integer $k$ ($1 \le k \le n$) such that $a_i$ is divisible by $a_k$ and $a_j$ is divisible by $a_k$ at the same time.

Please, find the number of good pairs.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2 \cdot 10^4$). The description of the test cases follows.

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

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

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

Output

For each test case, output the number of good pairs.

见题面 Input 部分

见题面 Output 部分

In the first test case, there are no good pairs.

In the second test case, here are all the good pairs: $(1, 2)$, $(2, 3)$, and $(2, 4)$.