Small GCD

$ a, b, c $ 为整数，定义 $ f(a, b, c) $ 如下: 将三个数排序，使得 $ a \le b \le c $。则函数返回 $ \gcd(a, b) $ , 这里 $ \gcd(a, b) $ 表示 [最大公约数 (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) 。简而言之，函数返回较小的两个数的最大公约数。 你会得到数组 $ 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)$。 【输入格式】 第一行一个整数 $ t \ ( 1 \le t \le 10 )$ 为数据组数。 每组数据第一行为 $ n \ (3 \le n \le 8 \cdot 10^4) $，第二行为 $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^5 $ ) 。 所有数据中 $ n $ 的和不超过 $ 8 \cdot 10^4 $。 【输出格式】 对每组数据，输出题中要求计算的求和。

Let $ a $ , $ b $ , and $ c $ be integers. We define function $ f(a, b, c) $ as follows: Order the numbers $ a $ , $ b $ , $ c $ in such a way that $ a \le b \le c $ . Then return $ \gcd(a, b) $ , where $ \gcd(a, b) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ a $ and $ b $ . So basically, we take the $ \gcd $ of the $ 2 $ smaller values and ignore the biggest one. You are given an array $ a $ of $ n $ elements. Compute the sum of $ f(a_i, a_j, a_k) $ for each $ i $ , $ j $ , $ k $ , such that $ 1 \le i < j < k \le n $ . More formally, compute $ $$$\sum_{i = 1}^n \sum_{j = i+1}^n \sum_{k =j +1}^n f(a_i, a_j, a_k). $ $$$

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

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

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 $ . The sum over all triples is $ 1+1+1+2+2+2+3+3+3+6=24 $ .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 $ .