E. Максимумы и минимумы
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых положительных чисел $$$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$$$.

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

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

Пример
Входные данные
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
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$$$, поэтому проверка пройдена.