The Honoured One#12366
Sign in

The Honoured One

2 seconds
256 megabytes
Medium

You are given an array consisting of integers. You have to count the number of distinct of un ordered pairs such that i < j and the values \gcd(a_i, a_j) among all chosen pairs.

Formally :

\#(\{\gcd(a_i,a_j) \ , 1 < i < j \le n \})

i.e. The count of distinct \gcd(a_i, a_j) among all pairs (1 \le i < j \le n) in the array .

Input

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

The first line of each test case contains a single integer (2 \le n \le 10^{5}) — the size of the array .

The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^5) — the elements of the array.

It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.

Output

For each test case, output a single integer — the number of satisfying pairs.

Examples

Example 1

Loading
Loading

Scoring

  1. Subtask ( points): (\sum n \le 2000)

  2. Subtask ( points): (a_i \le 100)

  3. Subtask ( points): (a_i \le 2000)

  4. Subtask ( points): No additional constraints