B. Всё везде
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив называется хорошим, если разность между максимальным и минимальным значениями в массиве равна наибольшему общему делителю (НОД) всех элементов массива. Обратите внимание, что пустой массив считается не хорошим.

Более формально, массив $$$[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).$$$$$$

Вам дана перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$. Определите количество хороших подмассивов$$$^{\text{†}}$$$ в данной перестановке.

$$$^{\text{∗}}$$$Перестановкой длины $$$m$$$ является массив, состоящий из $$$m$$$ различных целых чисел от $$$1$$$ до $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество хороших подмассивов в данной перестановке.

Пример
Входные данные
3
2
1 2
9
6 1 5 9 4 7 2 8 3
4
1 2 3 4
Выходные данные
1
0
3
Примечание

Для первого набора входных данных хорошим является только один подмассив: $$$[1, 2]$$$.

Для второго набора входных данных можно доказать, что в данной перестановке хороших подмассивов не существует.