CF2226B.Everything Everywhere

An array is called good if the difference between the maximum value and the minimum value in the array is equal to the greatest common divisor (GCD) of all the elements in the array. Note that an empty array is considered to be not good.

More formally, an array $[a_1, a_2, \ldots, a_m]$ is good if and only if $$ \max(a_1, a_2, \ldots, a_m) - \min(a_1, a_2, \ldots, a_m) = \gcd(a_1, a_2, \ldots, a_m).$$

You are given a permutation$^{\text{∗}}$ $p$ of length $n$. Determine the number of good subarrays$^{\text{†}}$ in the given permutation.

$^{\text{∗}}$A permutation of length $m$ is an array consisting of $m$ distinct integers from $1$ to $m$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($m=3$ but there is $4$ in the array).

$^{\text{†}}$An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

如果一个数组中最大值与最小值的差等于该数组所有元素的最大公约数（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$ 的一个子数组。特别地，一个数组是其自身的子数组。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each testcase contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the permutation $p$.

The second line of each testcase contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the permutation $p$. It is guaranteed that $p$ is a permutation.

It is guaranteed that the sum of $n$ over all the test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each testcase, print a single integer — the number of good subarrays in the given permutation.

对于每个测试用例，输出一个整数——给定排列中“好”子数组的个数。

For the first testcase, only one subarray is good, which is $[1, 2]$.

For the second testcase, it can be proven that no good subarrays exist in the given permutation.

对于第一个测试用例，只有一个好子数组，即 $[1, 2]$。

对于第二个测试用例，可以证明在给定的排列中不存在好子数组。