给定一个正整数数组 $$$a_1, a_2, \ldots, a_n$$$。
查找通过检查的索引对 $$$(l, r)$$$ 的数量,其中 $$$1 \le l \le r \le n$$$。检查按以下方式进行:
1. 在 $$$a_l, a_{l+1}, \ldots, a_r$$$ 中找到最小和最大数字。
2. 如果最大数能被最小数整除,则检查通过。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。然后是测试用例。
每个测试用例由两行组成。
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 数组的大小。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 通过检查的索引对的数量。
示例
输入 #1
6 1 1 2 2 4 2 2 3 4 2 4 7 14 7 16 5 18 7 7 12 14 6 16 14 2 6 16 2
输出 #1
1 3 2 7 10 19
注意
$$$x \mid y$$$ 下方表示 $$$y$$$ 可以被 $$$x$$$ 整除。
第一个测试用例中有一对$$$(1, 1)$$$,该对的最大值是$$$1$$$,最小值也是$$$1$$$,$$$1 \mid 1$$$,所以检查通过,答案是$$$1$$$。
在第二个测试用例中,有 $$$3$$$ 段:
- $$$(1, 1)$$$:最大值为$$$2$$$,最小值为$$$2$$$,$$$2 \mid 2$$$,因此检查通过。
- $$$(1, 2)$$$:最大为$$$4$$$,最小为$$$2$$$,$$$2 \mid 4$$$,因此检查通过。
- $$$(2, 2)$$$:最大值为$$$4$$$,最小值为$$$4$$$,$$$4 \mid 4$$$,因此检查通过。
在第三个测试用例中,有 $$$3$$$ 段:
- $$$(1, 1)$$$:最大值为$$$2$$$,最小值为$$$2$$$,$$$2 \mid 2$$$,因此检查通过。
- $$$(1, 2)$$$:最大值为$$$3$$$,最小值为$$$2$$$,$$$3$$$不能被$$$2$$$整除,因此检查失败。
- $$$(2, 2)$$$:最大值为$$$3$$$,最小值为$$$3$$$,$$$3 \mid 3$$$,因此检查通过。