题目描述

给你一个序列$N$为$A_{1},A_{2}...A_{N}$,请问有多少对$[L,R](L<R)$满足

$$Lcm\left (A_{L},A_{L+1}...A_{R}\right) \le\prod_{i=L}^{R} A_{i} $$

$Lcm\left (A_{L},A_{L+1}...A_{R} \right )$是求$A_{L}$到$A_{R}$所有数的最小公倍数
$gcd(A_{L},A_{L+1}...A_{R})$是求$A_{L}$到$A_{R}$所有数的最大公约数
$\prod_{i=L}^{R} A_{i}$是$A_{L}$到$A_{R}$的累积

输入格式

第一行包含一个整数 $T (1≤T≤10^{3})$—测试用例的数量。
每一个测试用例有两行:
第一行一个整数$N$表示序列的长度$(2 \le N \le 10^{3})$
第二行$N$个整数$N$表示序列的元素 $A_{1},A_{2}...A_{N}$$(1 \le A_{i} \le 10^{3})$

输出格式

共$T$行,每行一个整数表示该序列中满足条件$[L,R]$的数量

样例

2
3
1 2 3
2
3 9

3
1

解释:
对于第一个样例:
$[1,2]$:$Lcm\left (A_{1},A_{2}\right)=2$,$\prod_{i=1}^{2} A_{i}=2$
$[2,3]$:$Lcm\left(A_{2},A_{3}\right)=6$,$\prod_{i=1}^{2} A_{i}=6$
$[1,3]$:$Lcm\left(A_{1},A_{2},A_{3}\right)=6$,$\prod_{i=1}^{3} A_{i}=6$
对于第二个样例:
$[1,2]$:$Lcm\left (A_{1},A_{2}\right)=9$,$\prod_{i=1}^{2} A_{i}=27$



$Tip$:

$$Lcm\left (a,b \right )=\frac{a\cdot b}{gcd\left (a,b\right )} $$