Strange Definition
Contest: Codeforces Round 694 (Div. 1)
Difficulty rating: 1900
Tags: bitmasks, graphs, hashing, math, number theory

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.

Input format:
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 format:
For each query output a single integer — the beauty of the array at the corresponding moment.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1

Example output:
2
3

Editorial:
It is well known that $$$lcm(x, y)=\frac{x \cdot y}{gcd(x, y)}$$$, and it immediately follows that $$$\frac{lcm(x, y)}{gcd(x, y)}$$$ $$$=$$$ $$$\frac{x \cdot y}{gcd(x, y)^2}$$$, which means that numbers $$$x$$$ and $$$y$$$ are adjacent if and only if $$$x \cdot y$$$ is a perfect square.
Let $$$alpha_x$$$ be the maximum possible integer such that $$$p^{alpha_x}$$$ divides $$$x$$$, and $$$alpha_y$$$ be the maximum possible integer such that $$$p^{alpha_y}$$$ divides $$$y$$$. Then $$$x \cdot y$$$ is perfect square if and only if $$$\alpha_x + \alpha_y$$$ is even, which means $$$\alpha_x \equiv \alpha_y$$$ (mod $$$2$$$).
Let $$$x =p_1^{\alpha1} \cdot \ldots \cdot p_k^{\alpha_k}$$$. Let's replace it with $$$p_1^{\alpha1\bmod2} \cdot \ldots \cdot p_k^{\alpha_k\bmod2}$$$. After such a replacement two integers are adjacent if and only if they are equal.
Let's replace each element of the array and split the numbers into classes of equal numbers. If the number of integers in a single class is even, after a single operation each element from this class will be transformed to $$$1$$$, and if the number of integers is odd, the class of the element will remain unchanged. Since the class of integer 1 always remains unchanged, all integers will keep their classes starting from after the first operation.
Since $$$d_i$$$ denotes the size of the class, the beauty of the array is defined as the size of the maximal class. If $$$a$$$ if the size of the maximal class at the beginning of the process, and $$$b$$$ — the total number of elements with a class of even size or with the class equal to 1. Then for a query with $$$w = 0$$$ the answer is $$$a$$$, for a query with $$$w > 0$$$ the answer is $$$max(a, b)$$$.
This solution can easily be implemented with $$$O(n\log{A})$$$ complexity, where $$$A$$$ denotes the maximum number in the array.