给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。您可以对其进行如下操作:
1. 选择一对元素 $$$a_i$$$ 和 $$$a_j$$$ ($$$1 \le i, j \le n$$$ 和 $$$i \neq j$$$);
2. 选择整数 $$$a_i$$$ 的约数之一,即整数 $$$x$$$ 使得 $$$a_i \bmod x = 0$$$;
3. 将 $$$a_i$$$ 替换为 $$$\frac{a_i}{x}$$$,并将 $$$a_j$$$ 替换为 $$$a_j \cdot x$$$。
例如,我们考虑数组 $$$a$$$ = [$$$100, 2, 50, 10, 1$$$] 和 $$$5$$$ 元素。对其执行两个操作:
1. 选择 $$$a_3 = 50$$$ 且 $$$a_2 = 2$$$、$$$x = 5$$$。将 $$$a_3$$$ 替换为 $$$\frac{a_3}{x} = \frac{50}{5} = 10$$$,并将 $$$a_2$$$ 替换为 $$$a_2 \cdot x = 2 \cdot 5 = 10$$$。结果数组是 $$$a$$$ = [$$$100, 10, 10, 10, 1$$$];
2. 选择 $$$a_1 = 100$$$ 且 $$$a_5 = 1$$$、$$$x = 10$$$。将 $$$a_1$$$ 替换为 $$$\frac{a_1}{x} = \frac{100}{10} = 10$$$,并将 $$$a_5$$$ 替换为 $$$a_5 \cdot x = 1 \cdot 10 = 10$$$。结果数组是 $$$a$$$ = [$$$10, 10, 10, 10, 10$$$]。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) — 测试用例的数量。
然后是每个测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^4$$$) — 数组 $$$a$$$ 中的元素数量。
每个测试用例的第二行恰好包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^6$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。
输出
对于每个测试用例,输出一行:
- 如果可以通过应用一定次数(可能为零)的操作使数组中的所有元素相等,则为“是”;
- 否则为“否”。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”都将被识别为肯定答案)。
示例
输入 #1
7 5 100 2 50 10 1 3 1 1 1 4 8 2 4 2 4 30 50 27 20 2 75 40 2 4 4 3 2 3 1
输出 #1
YES YES NO YES NO YES NO
注意
第一个测试用例在问题陈述中进行了解释。