I. 最佳阵型
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

猪猪学院的魔法师小猪们正在研究一种全新的防御法阵，为小猪提供防御力。

共有 $$$n$$$ 只小猪排成一排，从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 只小猪的魔力值为 $$$a_i$$$。

对于区间 $$$[l, r]$$$（$$$1 \le l \le r \le n$$$）：

  • 定义它的稳定度为区间内所有魔力值的最小值，即 $$$\min\limits_{l \leq i \leq r} a_i$$$；
  • 定义它的共鸣值为区间最左和最右两个数的最大公约数，即 $$$\gcd(a_l, a_r)$$$；
  • 如果一个区间的稳定度等于共鸣值，那么这个区间被称为一个「和谐区间」。

这个防御法阵有如下效果：如果第 $$$i$$$ 只小猪身处 $$$k$$$ 个互不相同$$$^{\text{∗}}$$$的「和谐区间」内，那么它能提供 $$$k$$$ 点防御力。

整个队列的防御力定义为所有小猪提供的防御力之和。

为了找到最佳阵型，魔法师小猪们想要尝试不同的队列，使防御力尽可能大。

给定一组小猪队列，请你计算它的防御力。

$$$^{\text{∗}}$$$两个区间 $$$[l_1,r_1]$$$ 和 $$$[l_2,r_2]$$$ 被认为互不相同，当且仅当 $$$l_1\ne l_2$$$ 或 $$$r_1\ne r_2$$$。

Input

本题的输入包含多组测试用例。

第一行一个整数 $$$T$$$（$$$1 \leq T \leq 100$$$），表示测试用例的数量。对于每组测试用例：

  • 第一行一个整数 $$$n$$$（$$$1 \le n \le 10^5$$$），表示小猪的数量；
  • 第二行 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$（$$$1 \le a_i \le 3 \times 10^4$$$），表示每只小猪的魔力值。

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

Output

对于每组测试用例，输出一行，包含一个整数，表示该队列的防御力。

可以证明，在本题数据范围下，答案可以用 64 位有符号整数表示。

Example
Input
4
3
1 1 2
4
1 2 3 4
8
6 7 12 6 18 3 9 15
12
12 1 18 6 30 5 10 15 3 21 14 28
Output
10
16
86
147
Note

对于第一组测试用例，小猪的魔力值依次为 $$$[1, 1, 2]$$$。第 $$$1$$$ 只小猪身处 $$$3$$$ 个「和谐区间」$$$[1, 1]$$$、$$$[1, 2]$$$、$$$[1, 3]$$$ 中，提供 $$$3$$$ 点防御力；第 $$$2$$$ 只小猪身处 $$$4$$$ 个「和谐区间」$$$[1, 2]$$$、$$$[1, 3]$$$、$$$[2, 2]$$$、$$$[2, 3]$$$ 中，提供 $$$4$$$ 点防御力；第 $$$3$$$ 只小猪身处 $$$3$$$ 个「和谐区间」$$$[1, 3]$$$、$$$[2, 3]$$$、$$$[3, 3]$$$ 中，提供 $$$3$$$ 点防御力。总防御力为 $$$3 + 4 + 3 = 10$$$。

对于第二组测试用例，小猪的魔力值依次为 $$$[1, 2, 3, 4]$$$。第 $$$1$$$ 只小猪身处 $$$4$$$ 个「和谐区间」$$$[1, 1]$$$、$$$[1, 2]$$$、$$$[1, 3]$$$、$$$[1, 4]$$$ 中，提供 $$$4$$$ 点防御力；第 $$$2$$$ 只小猪身处 $$$5$$$ 个「和谐区间」$$$[1, 2]$$$、$$$[1, 3]$$$、$$$[1, 4]$$$、$$$[2, 2]$$$、$$$[2, 4]$$$ 中，提供 $$$5$$$ 点防御力；第 $$$3$$$ 只小猪身处 $$$4$$$ 个「和谐区间」$$$[1, 3]$$$、$$$[1, 4]$$$、$$$[2, 4]$$$、$$$[3, 3]$$$ 中，提供 $$$4$$$ 点防御力；第 $$$4$$$ 只小猪身处 $$$3$$$ 个「和谐区间」$$$[1, 4]$$$、$$$[2, 4]$$$、$$$[4, 4]$$$ 中，提供 $$$3$$$ 点防御力。总防御力为 $$$4 + 5 + 4 + 3 = 16$$$。

对于第三组测试用例，第 $$$1$$$ 至第 $$$8$$$ 只小猪身处的「和谐区间」数量依次为 $$$7$$$、$$$7$$$、$$$12$$$、$$$15$$$、$$$15$$$、$$$14$$$、$$$10$$$、$$$6$$$，总防御力为 $$$7 + 7 + 12 + 15 + 15 + 14 + 10 + 6 = 86$$$。

对于第四组测试用例，第 $$$1$$$ 至第 $$$12$$$ 只小猪身处的「和谐区间」数量依次为 $$$3$$$、$$$13$$$、$$$16$$$、$$$18$$$、$$$19$$$、$$$18$$$、$$$15$$$、$$$15$$$、$$$14$$$、$$$9$$$、$$$4$$$、$$$3$$$，总防御力为 $$$3 + 13 + 16 + 18 + 19 + 18 + 15 + 15 + 14 + 9 + 4 + 3 = 147$$$。