Andeviking学数学

描述

Andeviking 表示自己已经江郎才尽，编不出有趣的背景了。

给定一个长度为 $n$ 正整数序列 $A$ ，请求出下列式子的值：

$$\sum_{i=1}^{n}\sum_{j=i}^{n}[\min\{A_i , A_{i+1} , \cdots , A_{j-1} , A_{j}\} | \gcd(A_i , A_j)] $$

下面为公式中包含的某些符号进行解释：

• $gcd(a,b)$ 表示 $a$ 与 $b$ 的最大公因数
• $a|b$ 表示 $a$ 是 $b$ 的因数
• $[ a | b ]$ 表示当 $a$ 是 $b$ 的因数时值为 1 ，若不是则为 0
• $\min\{a,b,c, \cdots\}$ 表示 $a , b , c , \cdots$ 中的最小值

输入数据

第一行一个正整数 $T$ $(1\leq T \leq 10^4)$，代表数据组数

每组数据中第一行一个正整数 $n$ $(1 \leq n \leq 10^5)$ ，表示正整数序列 $A$ 的长度

接下来一行 $n$ 个以空格分隔的正整数表示 $A_1,A_2,\cdots,A_n$ $(1 \leq A_i \leq n)$

数据保证 $\sum_{i=1}^T n_i \leq 10^5$

输出数据

输出T行，每行一个正整数表示该组数据的答案

样例输入

2
3
2 1 3
3
1 2 3

样例输出

6
5