Назовем массив $$$b_1, b_2, \ldots, b_m$$$ хорошим, если существуют индексы $$$i < j$$$ такие, что $$$b_i \cdot b_j$$$ является полным квадратом.
В массиве $$$b_1, b_2, \ldots, b_m$$$ за одну операцию можно совершить одно из действий:
Обозначим $$$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$$$.
