D. Counting Rhyme
dp; math; number theory
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.
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\).
For each test case, output the number of good pairs.
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)\).