codeforces#P1470B. Strange Definition
Strange Definition
Description
Let us call two integers $x$ and $y$ adjacent if $\frac{lcm(x, y)}{gcd(x, y)}$ is a perfect square. For example, $3$ and $12$ are adjacent, but $6$ and $9$ are not.
Here $gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$, and $lcm(x, y)$ denotes the least common multiple (LCM) of integers $x$ and $y$.
You are given an array $a$ of length $n$. Each second the following happens: each element $a_i$ of the array is replaced by the product of all elements of the array (including itself), that are adjacent to the current value.
Let $d_i$ be the number of adjacent elements to $a_i$ (including $a_i$ itself). The beauty of the array is defined as $\max_{1 \le i \le n} d_i$.
You are given $q$ queries: each query is described by an integer $w$, and you have to output the beauty of the array after $w$ seconds.
The first input line contains a single integer $t$ ($1 \le t \le 10^5)$ — the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of the array.
The following line contains $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le 10^6$) — array elements.
The next line contain a single integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.
The following $q$ lines contain a single integer $w$ each ($0 \le w \le 10^{18}$) — the queries themselves.
It is guaranteed that the sum of values $n$ over all test cases does not exceed $3 \cdot 10^5$, and the sum of values $q$ over all test cases does not exceed $3 \cdot 10^5$
For each query output a single integer — the beauty of the array at the corresponding moment.
Input
The first input line contains a single integer $t$ ($1 \le t \le 10^5)$ — the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of the array.
The following line contains $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le 10^6$) — array elements.
The next line contain a single integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.
The following $q$ lines contain a single integer $w$ each ($0 \le w \le 10^{18}$) — the queries themselves.
It is guaranteed that the sum of values $n$ over all test cases does not exceed $3 \cdot 10^5$, and the sum of values $q$ over all test cases does not exceed $3 \cdot 10^5$
Output
For each query output a single integer — the beauty of the array at the corresponding moment.
Samples
2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1
2
3
Note
In the first test case, the initial array contains elements $[6, 8, 4, 2]$. Element $a_4=2$ in this array is adjacent to $a_4=2$ (since $\frac{lcm(2, 2)}{gcd(2, 2)}=\frac{2}{2}=1=1^2$) and $a_2=8$ (since $\frac{lcm(8,2)}{gcd(8, 2)}=\frac{8}{2}=4=2^2$). Hence, $d_4=2$, and this is the maximal possible value $d_i$ in this array.
In the second test case, the initial array contains elements $[12, 3, 20, 5, 80, 1]$. The elements adjacent to $12$ are $\{12, 3\}$, the elements adjacent to $3$ are $\{12, 3\}$, the elements adjacent to $20$ are $\{20, 5, 80\}$, the elements adjacent to $5$ are $\{20, 5, 80\}$, the elements adjacent to $80$ are $\{20, 5, 80\}$, the elements adjacent to $1$ are $\{1\}$. After one second, the array is transformed into $[36, 36, 8000, 8000, 8000, 1]$.