F. Никто не нужен
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Олег в подарок на день рождения получил перестановку $$$a$$$ длины $$$n$$$.

Друг Олега Нечипор задает Олегу $$$q$$$ вопросов, каждый вопрос характеризуется двумя числами $$$l$$$ и $$$r$$$, в ответ на вопрос Олег должен сказать количество наборов индексов $$$(t_1, t_2, \ldots, t_k)$$$ произвольной длины $$$k \ge 1$$$ таких, что:

  • $$$l \le t_i \le r$$$ для каждого $$$i$$$ от $$$1$$$ до $$$k$$$.
  • $$$t_i < t_{i+1}$$$ для каждого $$$i$$$ от $$$1$$$ до $$$k-1$$$.
  • $$$a_{t_{i+1}}$$$ делится на $$$a_{t_i}$$$ для каждого $$$i$$$ от $$$1$$$ до $$$k-1$$$.

Помогите Олегу и ответьте на все вопросы Нечипора.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — длина перестановки и количество вопросов Нечипора.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — сама перестановка $$$a$$$.

В каждой из следующих $$$q$$$ строк каждого набора входных данных содержатся два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — очередной вопрос Нечипора.

Гарантируется, что сумма значений $$$n$$$ и сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

Пример
Входные данные
4
8 8
2 1 6 3 5 4 8 7
1 8
2 8
1 7
1 6
1 3
5 8
4 4
2 3
1 1
1
1 1
3 3
3 2 1
1 2
1 3
2 3
8 1
1 2 3 4 5 6 7 8
1 8
Выходные данные
20 15 18 12 5 5 1 3
1
2 3 2
27
Примечание

Все подходящие массивы в первом наборе входных данных: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 3$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 6, 7$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 5$$$), ($$$2, 6$$$), ($$$2, 7$$$), ($$$2, 8$$$), ($$$2, 6, 7$$$), ($$$6, 7$$$).

Все подходящие массивы в четвертом наборе входных данных: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 2$$$), ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 5$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 8$$$), ($$$1, 2, 4$$$), ($$$1, 2, 6$$$), ($$$1, 2, 8$$$), ($$$1, 2, 4, 8$$$), ($$$1, 3, 6$$$), ($$$1, 4, 8$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$2, 8$$$), ($$$2, 4, 8$$$), ($$$3, 6$$$), ($$$4, 8$$$).