310772: CF1884D. Counting Rhyme

D. Counting Rhymetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExampleInput

6
4
2 4 4 4
4
2 3 4 4
9
6 8 9 4 6 8 9 4 9
9
7 7 4 4 9 9 6 2 9
18
10 18 18 15 14 4 5 6 8 9 10 12 15 16 18 17 13 11
21
12 19 19 18 18 12 2 18 19 12 12 3 12 12 12 18 19 16 18 19 12

Output

0
3
26
26
124
82

Note

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

题目大意：
给定一个整数数组 \(a_1, a_2, \ldots, a_n\)。如果存在一个整数对 \((i, j)\)，满足 \(1 \le i < j \le n\)，并且不存在整数 \(k\) (\(1 \le k \le n\)) 使得 \(a_i\) 和 \(a_j\) 同时能被 \(a_k\) 整除，则称这样的整数对为“好对”。请找出“好对”的数量。

输入输出数据格式：
输入：
- 第一行包含一个整数 \(t\)（\(1 \le t \le 2 \cdot 10^4\)），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数 \(n\)（\(1 \le n \le 10^6\)）。
- 第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)（\(1 \le a_i \le n\)）。
- 所有测试用例的 \(n\) 之和不超过 \(10^6\)。

输出：
- 对于每个测试用例，输出一个好对的数量。

示例：
输入：
```
6
4
2 4 4 4
4
2 3 4 4
9
6 8 9 4 6 8 9 4 9
9
7 7 4 4 9 9 6 2 9
18
10 18 18 15 14 4 5 6 8 9 10 12 15 16 18 17 13 11
21
12 19 19 18 18 12 2 18 19 12 12 3 12 12 12 18 19 16 18 19 12
```
输出：
```
0
3
26
26
124
82
```

注意：
- 在第一个测试用例中，没有好对。
- 在第二个测试用例中，所有的好对为 \((1, 2)\), \((2, 3)\), 和 \((2, 4)\)。题目大意： 给定一个整数数组 \(a_1, a_2, \ldots, a_n\)。如果存在一个整数对 \((i, j)\)，满足 \(1 \le i < j \le n\)，并且不存在整数 \(k\) (\(1 \le k \le n\)) 使得 \(a_i\) 和 \(a_j\) 同时能被 \(a_k\) 整除，则称这样的整数对为“好对”。请找出“好对”的数量。 输入输出数据格式： 输入： - 第一行包含一个整数 \(t\)（\(1 \le t \le 2 \cdot 10^4\)），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数 \(n\)（\(1 \le n \le 10^6\)）。 - 第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)（\(1 \le a_i \le n\)）。 - 所有测试用例的 \(n\) 之和不超过 \(10^6\)。 输出： - 对于每个测试用例，输出一个好对的数量。 示例： 输入： ``` 6 4 2 4 4 4 4 2 3 4 4 9 6 8 9 4 6 8 9 4 9 9 7 7 4 4 9 9 6 2 9 18 10 18 18 15 14 4 5 6 8 9 10 12 15 16 18 17 13 11 21 12 19 19 18 18 12 2 18 19 12 12 3 12 12 12 18 19 16 18 19 12 ``` 输出： ``` 0 3 26 26 124 82 ``` 注意： - 在第一个测试用例中，没有好对。 - 在第二个测试用例中，所有的好对为 \((1, 2)\), \((2, 3)\), 和 \((2, 4)\)。