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.

我们称两个整数 $x$ 和 $y$ 是相邻的，如果 $\frac{\mathrm{lcm}(x, y)}{\gcd(x, y)}$ 是一个完全平方数。例如，$3$ 和 $12$ 是相邻的，但 $6$ 和 $9$ 不是。

此处，$\gcd(x, y)$ 表示整数 $x$ 与 $y$ 的最大公约数（GCD），$\mathrm{lcm}(x, y)$ 表示整数 $x$ 与 $y$ 的最小公倍数（LCM）。

给定一个长度为 $n$ 的数组 $a$。每一秒执行如下操作：数组中的每个元素 $a_i$ 被替换为数组中所有与当前值 $a_i$ 相邻的元素（包括 $a_i$ 自身）的乘积。

令 $d_i$ 表示与 $a_i$ 相邻的元素个数（包含 $a_i$ 自身）。数组的优美度（beauty） 定义为 $\max_{1 \le i \le n} d_i$。

你将收到 $q$ 个查询：每个查询由一个整数 $w$ 描述，你需要输出经过 $w$ 秒后数组的优美度。

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$

第一行输入包含一个整数 $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$。

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

在第一个测试用例中，初始数组包含元素 $[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]$。