Description

题面翻译

$a, b, c$ 为整数，定义 $f(a, b, c)$ 如下:

将三个数排序，使得 $a \le b \le c$。则函数返回 $\gcd(a, b)$ , 这里 $\gcd(a, b)$ 表示 最大公约数 (GCD) 。简而言之，函数返回较小的两个数的最大公约数。

你会得到数组 $a$，包含 $n$ 个元素。求 $f(a_i, a_j, a_k)$ 之和，其中 $1 \le i< j < k \le n$。

形式化的讲，求 $\sum_{i = 1}^n \sum_{j = i+1}^n \sum_{k =j +1}^n f(a_i, a_j, a_k)$。

Input

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

The first line of each test case contains a single integer $n$ ($3 \le n \le 8 \cdot 10^4$) — length of the array $a$.

The second line of each test case contains $n$ integers, $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$) — elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $8 \cdot 10^4$.

Output

For each test case, output a single number — the sum from the problem statement.

2
5
2 3 6 12 17
8
6 12 8 10 15 12 18 16
 
 

24
203

Note

In the first test case, the values of $f$ are as follows:

• $i=1$, $j=2$, $k=3$, $f(a_i,a_j,a_k)=f(2,3,6)=\gcd(2,3)=1$;
• $i=1$, $j=2$, $k=4$, $f(a_i,a_j,a_k)=f(2,3,12)=\gcd(2,3)=1$;
• $i=1$, $j=2$, $k=5$, $f(a_i,a_j,a_k)=f(2,3,17)=\gcd(2,3)=1$;
• $i=1$, $j=3$, $k=4$, $f(a_i,a_j,a_k)=f(2,6,12)=\gcd(2,6)=2$;
• $i=1$, $j=3$, $k=5$, $f(a_i,a_j,a_k)=f(2,6,17)=\gcd(2,6)=2$;
• $i=1$, $j=4$, $k=5$, $f(a_i,a_j,a_k)=f(2,12,17)=\gcd(2,12)=2$;
• $i=2$, $j=3$, $k=4$, $f(a_i,a_j,a_k)=f(3,6,12)=\gcd(3,6)=3$;
• $i=2$, $j=3$, $k=5$, $f(a_i,a_j,a_k)=f(3,6,17)=\gcd(3,6)=3$;
• $i=2$, $j=4$, $k=5$, $f(a_i,a_j,a_k)=f(3,12,17)=\gcd(3,12)=3$;
• $i=3$, $j=4$, $k=5$, $f(a_i,a_j,a_k)=f(6,12,17)=\gcd(6,12)=6$.

In the second test case, there are $56$ ways to choose values of $i$, $j$, $k$. The sum over all $f(a_i,a_j,a_k)$ is $203$.