调用一个数组 好 如果数组中最大值和最小值之间的差等于数组中所有元素的最大公约数 (GCD)。请注意,空数组被认为是不好的。
更正式地说,数组 $$$[a_1, a_2, \ldots, a_m]$$$ 是 好 当且仅当 $$\max(a_1, a_2, \ldots, a_m) - \min(a_1, a_2, \ldots, a_m) = \gcd(a_1, a_2, \ldots, a_m).$$
给你一个长度为 $$$n$$$ 的排列$$$^{\text{*}}$$$ $$$p$$$。确定给定排列中好的子数组$$$^{\text{†}}$$$ 的数量。
$$$^{\text{*}}$$$长度$$$m$$$的排列是一个由从$$$1$$$到$$$m$$$以任意顺序的$$$m$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$m=3$$$但数组中有$$$4$$$)。
$$$^{\text{†}}$$$数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。 特别是,数组是其自身的子数组。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 排列 $$$p$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$。保证 $$$p$$$ 是一个排列。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 给定排列中好的子数组的数量。
示例
输入复制
321 296 1 5 9 4 7 2 8 341 2 3 4
输出复制
103
注意
对于第一个测试用例,只有一个子数组是好的,即 $$$[1, 2]$$$。
对于第二个测试用例,可以证明给定的排列中不存在好的子数组。