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

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.

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

✓	#	Name		✎	Rating↕	Solved↕
	1731C	Even Subarrays bitmasks brute force hashing math number theory			1700	12.5k
	1470B	Strange Definition bitmasks graphs hashing math number theory			1900	6.8k

Problemset