设 $$$a$$$、$$$b$$$ 和 $$$c$$$ 为整数。我们定义函数 $$$f(a, b, c)$$$ 如下:
以 $$$a \le b \le c$$$ 的方式对数字 $$$a$$$、$$$b$$$、$$$c$$$ 进行排序。然后返回 $$$\gcd(a, b)$$$,其中 $$$\gcd(a, b)$$$ 表示整数 $$$a$$$ 和 $$$b$$$ 的最大公约数 (GCD)。
所以基本上,我们取 $$$2$$$ 较小值中的 $$$\gcd$$$ 并忽略最大的值。
给定一个由 $$$n$$$ 元素组成的数组 $$$a$$$。计算每个 $$$i$$$、$$$j$$$、$$$k$$$ 的 $$$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$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数,$$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$8 \cdot 10^4$$$。
输出
对于每个测试用例,输出一个数字 - 问题陈述的总和。
示例
输入 #1
2 5 2 3 6 12 17 8 6 12 8 10 15 12 18 16
输出 #1
24 203
注意
在第一个测试用例中,$$$f$$$ 的值如下:
- $$$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$$$。
在第二个测试用例中,有 $$$56$$$ 种方法来选择 $$$i$$$、$$$j$$$、$$$k$$$ 的值。所有 $$$f(a_i,a_j,a_k)$$$ 的总和为 $$$203$$$。