Женя подарил Бурёнке на день рождения массив \(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\).
Помогите Жене ответить на вопросы!
Выходные данные
Выведите \(q\) чисел — ответы на вопросы Бурёнки.
Примечание
Рассмотрим запросы из примера:
- в первом вопросе произведение чисел на первом отрезке равно \(1\), оно взаимно просто с числами \(1,2,3,4,5\).
- во втором вопросе произведение чисел на втором отрезке равно \(12\), оно взаимно просто с числами \(1\) и \(5\).
- в третьем вопросе произведение чисел на третьем отрезке равно \(10\), оно взаимно просто с числами \(1\) и \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5 5 3
1 2 3 2 5
1 1
2 4
4 5
|
5
2
2
|