H. Получить квадрат
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Назовем массив $$$b_1, b_2, \ldots, b_m$$$ хорошим, если существуют индексы $$$i < j$$$ такие, что $$$b_i \cdot b_j$$$ является полным квадратом.

В массиве $$$b_1, b_2, \ldots, b_m$$$ за одну операцию можно совершить одно из действий:

  • умножить некоторый элемент $$$b_i$$$ на некоторое простое $$$p$$$;
  • разделить некоторый элемент $$$b_i$$$ на некоторое простое $$$p$$$ такое, что $$$b_i$$$ делится на $$$p$$$.

Обозначим $$$f(b_1, b_2, \ldots, b_m)$$$ минимальное число действий, которые нужно совершить, чтобы сделать массив $$$b$$$ хорошим.

Вам дан массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ и $$$q$$$ запросов вида $$$l_i, r_i$$$. Для каждого запроса выведите $$$f(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i})$$$.

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

Первая строка содержит целые числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 194\,598$$$, $$$1 \le q \le 1\,049\,658$$$) — длина массива и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 5\,032\,107$$$) — элементы массива.

Каждая из следующих $$$q$$$ строк содержит 2 целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — параметры запроса.

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

Выведите $$$q$$$ строк — ответы на каждый запросы в том порядке, в котором они заданы во входных данных.

Пример
Входные данные
10 10
34 37 28 16 44 36 43 50 22 13
1 3
4 8
6 10
9 10
3 10
8 9
5 6
1 4
1 7
2 6
Выходные данные
2
0
1
3
0
1
1
1
0
0
Примечание

В первом запросе первого примера можно умножить второе число на 7 и получить 259, и умножить третье число на 37 и получить 1036. Тогда $$$a_2 \cdot a_3 = 268\,324 = 518^2$$$.

Во втором запросе подмассив уже хороший, потому что $$$a_4 \cdot a_6 = 24^2$$$.

В третьем запросе можно разделить 50 на 2 и получить 25. Тогда $$$a_6 \cdot a_8 = 30^2$$$.