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

Женя подарил Бурёнке на день рождения массив $$$a$$$ длины $$$n$$$ из чисел от $$$1$$$ до $$$m$$$. Бурёнка знает, что Жене очень нравятся взаимно простые числа (числа $$$x$$$ и $$$y$$$ называются взаимно простыми, если у них отсутствуют общие делители, большие $$$1$$$), поэтому она хочет задать Жене $$$q$$$ вопросов про свой подарок.

Каждый раз она будет выбирать какой-то подотрезок $$$a_l, a_{l + 1}, \ldots, a_r$$$ массива $$$a$$$ и вычислять произведение этих чисел $$$p = a_l \cdot a_{l + 1} \cdot \ldots \cdot a_r$$$. Затем она спросит у Жени, сколько целых чисел от $$$1$$$ до $$$C$$$ взаимно просты с числом $$$p$$$.

Помогите Жене ответить на вопросы!

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

В первой строке ввода находятся четыре числа $$$n$$$, $$$m$$$, $$$C$$$, $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$, $$$1 \leq m \leq 2\cdot 10^4$$$, $$$1 \leq C \leq 10^5$$$) — длина массива $$$a$$$, верхнее ограничения на $$$a_{i}$$$, значение $$$C$$$ и количество запросов.

Во второй строке ввода находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_{i} \leq m$$$) — массив $$$a$$$.

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

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

Выведите $$$q$$$ чисел — ответы на вопросы Бурёнки.

Пример
Входные данные
5 5 5 3
1 2 3 2 5
1 1
2 4
4 5
Выходные данные
5
2
2
Примечание

Рассмотрим запросы из примера:

  1. в первом вопросе произведение чисел на первом отрезке равно $$$1$$$, оно взаимно просто с числами $$$1,2,3,4,5$$$.
  2. во втором вопросе произведение чисел на втором отрезке равно $$$12$$$, оно взаимно просто с числами $$$1$$$ и $$$5$$$.
  3. в третьем вопросе произведение чисел на третьем отрезке равно $$$10$$$, оно взаимно просто с числами $$$1$$$ и $$$3$$$.