题目描述

设 $a$ , $b$ 和 $c$ 为整数。我们将函数 $f(a, b, c)$ 定义如下：

将数字 $a$ 、$b$ 、$c$ 排序为 $a \le b \le c$ 。然后返回 $\gcd(a, c)$ ，其中 $\gcd(a, c)$ 表示整数 $a$ 和 $c$ 的最大公约数。

给你一个由 $n$ 个元素组成的数组 $a$ 。计算每个 $i$ , $j$ , $k$ 的 $f(a _ i, a _ j, a _ k)$ 的和，使得 $1 ≤ i < j < k ≤ n$。

更正式地说，请你计算 $ans = \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^5)$，测试用例说明如下：

每个测试用例的第一行都包含一个整数 $n$ $(1 \le n \le 10^5)$ - 数组长度 $a$ 。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, …, a_n$ 个整数 $(1 \le a_i \le 10^5)$ - 数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^5$ 。

输出格式

对于每个测试用例，输出一个数字，即问题陈述中的总和。

注意：答案可能极大，请使用合适的数据类型存储。

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

15
221