CF1470B.Strange Definition

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.

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]$ .