如果 $$$\frac{lcm(x, y)}{gcd(x, y)}$$$ 是完全平方数,我们称两个整数 $$$x$$$ 和 $$$y$$$ 相邻。例如,$$$3$$$ 和 $$$12$$$ 相邻,但 $$$6$$$ 和 $$$9$$$ 不相邻。
这里 $$$gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD),$$$lcm(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最小公倍数 (LCM)。
给定一个长度为 $$$n$$$ 的数组 $$$a$$$。每一秒都会发生以下情况:数组的每个元素 $$$a_i$$$ 被数组中与当前值相邻的所有元素(包括其本身)的乘积替换。
设 $$$d_i$$$ 为 $$$a_i$$$ 的相邻元素数(包括 $$$a_i$$$ 本身)。数组的美度定义为 $$$\max_{1 \le i \le n} d_i$$$。
给你$$$q$$$查询:每个查询由一个整数$$$w$$$描述,你必须在$$$w$$$秒后输出数组的美丽。
输入
第一个输入行包含一个整数 $$$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$$$
输出
对于每个查询输出一个整数——相应时刻数组的美丽。
示例
输入 #1
2 4 6 8 4 2 1 0 6 12 3 20 5 80 1 1 1
输出 #1
2 3
注意
在第一个测试用例中,初始数组包含元素 $$$[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]$$$。