B. Странное определение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём два числа $$$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$$$ секунд.

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

В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^5)$$$ — количество тестовых примеров.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длину массива.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива.

Следующая строка содержит целое число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — количество запросов.

Каждая из следующих $$$q$$$ строк содержит единственное целое число $$$w$$$ ($$$0 \le w \le 10^{18}$$$) — описание запроса.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$, и сумма значений $$$q$$$ по всем наборам входных данных также не превосходит $$$3 \cdot 10^5$$$

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

Для каждого запроса выведите одно число — красоту массива в соответствующий момент времени.

Пример
Входные данные
2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1
Выходные данные
2
3
Примечание

В первом наборе входных данных исходный массив состоит из чисел $$$[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]$$$.