В этот раз Ехаб решил только разрезать массив. Он начинает с массива \(a\) длины \(n\), записанного на полоске бумаги, и делает следующее:
- Ехаб выбирает отрезок \((l, r)\) и вырезает отрезок с элементами \(a_l, a_{l + 1}, \ldots, a_r\), выбрасывая остальные элементы.
- Затем он разрезает его на несколько подотрезков.
- Чтобы добавить интереса в это занятие, он требует, чтобы произведение элементов на каждом подотрезке было равно их наименьшему общему кратному (НОК).
Формально, он разбивает элементы \(a_l, a_{l + 1}, \ldots, a_r\) на подотрезки так, чтобы произведение элементов каждого подотрезка было равно НОК элементов этого подотрезка. У Ехаба есть \(q\) независимых отрезков \((l, r)\), для которых он хочет узнать, на какое минимальное число подотрезков их необходимо разрезать, чтобы условие выполнялось.
Выходные данные
Для каждого запроса выведите ответ на него.
Примечание
Первый запрос спрашивает про весь массив. Вы можете разделить его так: \([2]\), \([3,10,7]\), и \([5,14]\). Произведение и НОК первого подотрезка равны \(2\). Произведение и НОК второго подотрезка равны \(210\). И произведение и НОК третьего подотрезка равны \(70\). Существует другое возможное разделение: \([2,3]\), \([10,7]\), и \([5,14]\).
Второй запрос спрашивает про отрезок \((2,4)\). Его произведение уже равно его НОК, следовательно, не нужно делить его ни разу.
Последний запрос про отрезок \((3,5)\). Вы можете разделить его на \([10,7]\) и \([5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
2 3 10 7 5 14
1 6
2 4
3 5
|
3
1
2
|