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

В этот раз Ехаб решил только разрезать массив. Он начинает с массива $$$a$$$ длины $$$n$$$, записанного на полоске бумаги, и делает следующее:

  • Ехаб выбирает отрезок $$$(l, r)$$$ и вырезает отрезок с элементами $$$a_l, a_{l + 1}, \ldots, a_r$$$, выбрасывая остальные элементы.
  • Затем он разрезает его на несколько подотрезков.
  • Чтобы добавить интереса в это занятие, он требует, чтобы произведение элементов на каждом подотрезке было равно их наименьшему общему кратному (НОК).

Формально, он разбивает элементы $$$a_l, a_{l + 1}, \ldots, a_r$$$ на подотрезки так, чтобы произведение элементов каждого подотрезка было равно НОК элементов этого подотрезка. У Ехаба есть $$$q$$$ независимых отрезков $$$(l, r)$$$, для которых он хочет узнать, на какое минимальное число подотрезков их необходимо разрезать, чтобы условие выполнялось.

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

В первой строке записано $$$2$$$ целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n,q \le 10^5$$$) — длина массива $$$a$$$ и количество запросов.

Во второй строке записано $$$n$$$ целых чисел, $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^5$$$) — элементы массива $$$a$$$.

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

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

Для каждого запроса выведите ответ на него.

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

Первый запрос спрашивает про весь массив. Вы можете разделить его так: $$$[2]$$$, $$$[3,10,7]$$$, и $$$[5,14]$$$. Произведение и НОК первого подотрезка равны $$$2$$$. Произведение и НОК второго подотрезка равны $$$210$$$. И произведение и НОК третьего подотрезка равны $$$70$$$. Существует другое возможное разделение: $$$[2,3]$$$, $$$[10,7]$$$, и $$$[5,14]$$$.

Второй запрос спрашивает про отрезок $$$(2,4)$$$. Его произведение уже равно его НОК, следовательно, не нужно делить его ни разу.

Последний запрос про отрезок $$$(3,5)$$$. Вы можете разделить его на $$$[10,7]$$$ и $$$[5]$$$.