Назовём два числа \(x\) и \(y\) смежными, если \(\frac{lcm(x, y)}{gcd(x, y)}\) — полный квадрат. К примеру, \(3\) и \(12\) являются смежными, а \(6\) и \(9\) — нет.
Здесь \(gcd(x, y)\) обозначает наибольший общий делитель (НОД) чисел \(x\) и \(y\), а \(lcm(x, y)\) обозначает наименьшее общее кратное (НОК) чисел \(x\) и \(y\).
У вас есть массив \(a\) размера \(n\), и каждую секунду происходит следующее: каждый элемент массива \(a_i\) заменяется на произведение всех смежных с ним чисел из массива (включая и сам элемент \(a_i\)).
Пусть \(d_i\) — количество смежных с \(a_i\) чисел из массива (включая само число). Красота массива определяется как \(\max_{1 \le i \le n} d_i\). Вам даны \(q\) запросов, каждый из которых описывается числом \(w\). Для каждого запроса выведите красоту массива после \(w\) секунд.
Выходные данные
Для каждого запроса выведите одно число — красоту массива в соответствующий момент времени.
Примечание
В первом наборе входных данных исходный массив состоит из чисел \([6, 8, 4, 2]\). Элемент \(a_4=2\) в этом массиве является смежным с числами \(a_4=2\) (так как \(\frac{lcm(2, 2)}{gcd(2, 2)}=\frac{2}{2}=1=1^2\)) и \(a_2=8\) (так как \(\frac{lcm(8,2)}{gcd(8, 2)}=\frac{8}{2}=4=2^2\)). Таким образом, \(d_4=2\), и это максимальное значение \(d_i\) среди элементов данного массива.
Во втором наборе входных данных исходный массив состоит из чисел \([12, 3, 20, 5, 80, 1]\). Элементы, смежные с \(12\), это \(\{12, 3\}\), смежные с \(3\) — \(\{12, 3\}\), смежные с \(20\) — \(\{20, 5, 80\}\), смежные с \(5\) — \(\{20, 5, 80\}\), смежные с \(80\) — \(\{20, 5, 80\}\), смежные с \(1\) — \(\{1\}\). Через одну секунду массив превращается в \([36, 36, 8000, 8000, 8000, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1
|
2
3
|