背景

题目来源：【HT-130-Div.3】核桃 CSP-J 组模拟赛

LAOI 欢迎您。

题目描述

在变完魔术以后，小 Hex 和小 Toast 又开始玩起了他的积木。

小 Hex 把他的所有积木整理起来，按美丽度从大到小的顺序把他的所有积木排成一行。此时排序后第 $i$ 块积木的美丽度为 $b_i$。现在小 Hex 想把他的一段连续区间的所有积木拼成一座积木塔，并邀请小 Toast 观赏。

然而小 Toast 对积木塔有着独特的审美。小 Toast 计算一段区间 $[l,r]$ 的积木的「奇异值（$t$）」的方法如下：

• 首先，小 Hex 拿出了第 $l$ 块积木
  • 此时令 $t=a_l$。
• 接下来，小 Hex 会依次将第 $l+1$，第 $l+2$，$\cdots$，第 $r$ 块积木拼在现有的积木塔上。假设小 Hex 目前在拼接第 $i$ 块积木。
  • 此时令 $t\gets \lfloor\frac{\max(t,a_i)}{\min(t,a_i)}\rfloor$。

最终，如果奇异值 $t$ 为 $1$，那么小 Toast 则称这段区间是好的。现在小 Toast 想要知道，对于所有的 $1\leq l \leq r \leq n$，有多少段区间是好的？

简要题意

多次询问，每次给定一个单调不增的序列 $b$，对于 $b$ 的一个非空区间 $[l,r]$，初始时令变量 $t=b_l$。从 $l+1$ 到 $r$ 枚举下标 $i$，依次执行操作 $t:=\lfloor\frac{\max(t,b_i)}{\min(t,b_i)}\rfloor$，所有操作完成后最终 $t=1$，则称这个区间是好的。

现询问 $A$ 有多少个非空区间是好的。

输入格式

本题有多组测试数据。

第一行给定一个正整数 $T$，表示数据组数。

对于每组数据：

• 第一行输入一个正整数 $n$，表示序列长度；
• 第二行输入 $n$ 个正整数，表示序列 $b$。

输出格式

共 $T$ 行，对于每组测试数据，输出一个整数表示答案。

3
3
3 2 2
1
5
5
6 4 3 2 1

2
0
7

2
7
30 19 9 8 5 4 1
4
12 11 10 9

12
4

提示

【样例 1 解释】

• 对于第一组测试数据，好的区间有 $[1,2]$、$[2,3]$；
  • 如果区间为 $[1,2]$，那么初始时 $t=3$，拼接第 $2$ 块积木时，$t\gets \lfloor\frac{\max(3,2)}{\min(3,2)}\rfloor=\lfloor\frac{3}{2}\rfloor=1$。因此这个区间是好的。
  • 如果区间为 $[2,3]$，那么初始时 $t=2$，拼接第 $3$ 块积木时，$t\gets \lfloor\frac{\max(2,2)}{\min(2,2)}\rfloor=\lfloor\frac{2}{2}\rfloor=1$。因此这个区间是好的。
• 对于第二组测试数据，可以证明不存在好的区间。
• 对于第三组测试数据，好的区间有 $[1,2]$、$[1,4]$、$[2,3]$、$[1,5]$、$[3,4]$、$[3,5]$、$[5,5]$。

【样例 3】

见选手目录下的 block/block3.in 与 block/block3.ans。

该样例满足测试点 $1$ 的约束条件。

【样例 4】

见选手目录下的 block/block4.in 与 block/block4.ans。

该样例满足测试点 $2,3$ 的约束条件。

【样例 5】

见选手目录下的 block/block5.in 与 block/block5.ans。

该样例满足测试点 $4\sim 6$ 的约束条件。

【样例 6】

见选手目录下的 block/block6.in 与 block/block6.ans。

该样例满足测试点 $7,8$ 的约束条件。

【样例 7】

见选手目录下的 block/block7.in 与 block/block7.ans。

该样例满足测试点 $9\sim 11$ 的约束条件。

【样例 8】

见选手目录下的 block/block8.in 与 block/block8.ans。

该样例满足测试点 $12\sim 20$ 的约束条件。

【数据范围】

对于所有测试数据，保证 $1\le T\le 10^6$，$1\le n,\sum n \le 10^6$，$1\le b_i\le 10^9$。

为表述方便，下面记 $\sum n$ 为测试点内所有 $n$ 之和。

::cute-table{tuack}

测试点编号	$n,\sum n$	特殊性质
$1$	$\le 5\times 10^2$	无
$2,3$	$\le 5\times 10^3$
$4\sim 6$	$\le 10^6$	A
$7,8$	^	B
$9\sim 11$		C
$12\sim 20$		无

特殊性质 A：对于所有的 $i(1\leq i\leq n)$，保证 $b_i=n-i+1$。

特殊性质 B：保证所有的 $b_i$ 相同。

特殊性质 C：对于所有的 $i(1\leq i\leq n)$，保证 $1\leq b_i\leq 20$。