### 问题描述 小然有一个由 $N$ 个不同的整数组成的数组 $A$。 在一次操作中，小然可以： 1. 选择数组中的任意两个相邻的元素 $A_i$ 和 $A_{i+1}$。 2. 计算出 $X = \gcd(A_i, A_{i+1})$ 和 $Y = \text{lcm}(A_i, A_{i+1})$，其中 $\gcd$ 表示最大公约数，$\text{lcm}$ 表示最小公倍数。 3. 将 $A_i$ 和 $A_{i+1}$ 替换为 $X$ 和 $Y$。 小然的目标是通过尽可能多的操作，使得数组 $A$ 的和尽可能大。 请你帮助小然找出在最优策略下，他能得到的数组和的最大值。 ### 输入格式 输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例由两行组成： - 第一行包含一个整数 $N$，表示数组的长度。 - 第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, ..., A_N$，表示数组 $A$。 ### 输出格式 对于每个测试用例，输出一行一个整数，表示最优策略下，小然能得到的数组和的最大值。由于这个值可能很大，你需要输出它模 $10^9 + 7$ 的结果。 ### 样例输入 ```text 3 4 4 4 6 1 3 108 24 18 10 93179 93187 93199 93229 93239 93241 93251 93253 93257 93263 ``` ### 样例输出 ```text 19 258 392286903 ``` ### 说明 在第一个测试用例中，我们可以进行以下操作： - 首先选择 $A_2 = 4$ 和 $A_3 = 6$，计算出 $X = \gcd(4, 6) = 2$ 和 $Y = \text{lcm}(4, 6) = 12$，然后将 $A_2$ 和 $A_3$ 替换为 $X$ 和 $Y$，得到新的数组 $A = [4, 2, 12, 1]$。数组的和为 $19$，可以证明这就是最大的数组和。 ### 评测数据范围 $1 \leq T \leq 10$。 $1 \leq N \leq 10^5$。 $1 \leq A_i \leq 10^6$。 所有测试用例 $N$ 的总和不会超过 $10^5$。