D. Ирис и соседние произведения
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ирис только что научилась умножению на уроках математики. Однако, поскольку её мозг не в состоянии выдерживать слишком сложные вычисления, она не может перемножать два целых числа, произведение которых больше $$$k$$$. В противном случае её мозг может взорваться!

Её учитель каждый день даёт ей сложную задачу в качестве домашнего задания на летних каникулах. Теперь ей дан массив $$$a$$$, состоящий из $$$n$$$ элементов, и ей нужно вычислить произведение каждой пары соседних элементов (то есть, $$$a_1 \cdot a_2$$$, $$$a_2 \cdot a_3$$$ и так далее). Ирис хочет, чтобы её мозг не перегружался, и для этого она хотела бы изменить массив $$$a$$$ так, чтобы выполнялось условие $$$a_i \cdot a_{i + 1} \leq k$$$ для всех $$$1 \leq i < n$$$. Она может выполнять два типа операций:

  1. Она может переставить элементы массива $$$a$$$ произвольным образом.
  2. Она может выбрать произвольный элемент массива $$$a$$$ и изменить его значение на произвольное целое число от $$$1$$$ до $$$k$$$.

Ирис хочет минимизировать количество операций типа $$$2$$$, которые она использует.

Однако это совершенно не конец летних каникул! Летние каникулы длятся $$$q$$$ дней, и в $$$i$$$-й день Ирис просят решить математическое задание для подмассива $$$b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}$$$. Помогите Ирис и скажите ей минимальное количество операций типа $$$2$$$, которые ей нужно выполнить для каждого дня. Обратите внимание, что операции независимы для каждого дня, то есть массив $$$b$$$ не изменяется.

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$q$$$ и $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$, $$$1 \leq k \leq 10^6$$$) — длина массива $$$b$$$, количество дней и верхняя граница для вычисления произведения.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq k$$$) — элементы массива $$$b$$$.

Затем следуют $$$q$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i < r_i \leq n$$$) — границы подмассива в $$$i$$$-й день.

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

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

Для каждого набора входных данных выведите одну строку, содержащую $$$q$$$ целых числа — минимальное количество операций типа $$$2$$$, необходимых для каждого дня.

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

В первом наборе входных данных, так как Ирис всегда может перемножить $$$1$$$ и $$$1$$$, операции не требуются, поэтому ответ равен $$$0$$$.

Во втором наборе входных данных, домашнее задание первого дня — $$$[1, 10, 9]$$$. Ирис может переставить его элементы, чтобы получить $$$[9, 1, 10]$$$, поэтому операции типа $$$2$$$ не требуются. Домашнее задание второго дня — $$$[10, 9]$$$, и она может изменить один элемент, чтобы получить массив $$$[1, 9]$$$, поэтому требуется одна операция типа $$$2$$$.