Назовем массив \(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})\).
Выходные данные
Выведите \(q\) строк — ответы на каждый запросы в том порядке, в котором они заданы во входных данных.
Примечание
В первом запросе первого примера можно умножить второе число на 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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|