Mocha喜欢数组,所以在她出发之前,378QAQ送给她一个由$$$n$$$正整数组成的数组$$$a$$$作为礼物。
Mocha 认为 $$$a$$$ 是美丽的,如果存在两个数字 $$$i$$$ 和 $$$j$$$ ($$$1\leq i,j\leq n$$$, $$$i\neq j$$$),这样对于所有 $$$k$$$ ($$$1 \leq k \leq n$$$),$$$a_k$$$ 是$$$^\dagger$$$ 可以被 $$$a_i$$$ 或 $$$a_j$$$ 整除。
判断$$$a$$$是否漂亮。
如果存在一个整数 $$$z$$$ 使得 $$$x = y \cdot z$$$,$$$^\dagger$$$ $$$x$$$ 可以被 $$$y$$$ 整除。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\leq t\leq 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3\leq n\leq 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,如果数组 $$$a$$$ 很漂亮,则输出“Yes”,否则输出“No”。
在任何情况下都可以输出“Yes”和“No”(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应)。
示例
输入 #1
4 3 7 3 8 5 7 1 9 3 5 5 4 12 2 6 3 5 7 49 9 3 1000000000
输出 #1
No Yes Yes No
注意
在第一个测试用例中,数组中的任何两个数字都是互质的,所以答案是“否”。
在第二个测试用例中,我们可以选择 $$$i=2$$$ 和 $$$j=1$$$。由于数组中的每个数字都可以被 $$$a_i = 1$$$ 整除,所以答案是“是”。
在第三个测试用例中,我们可以选择 $$$i=3$$$ 和 $$$j=5$$$。 $$$2$$$ 和 $$$4$$$ 可以被 $$$a_i = 2$$$ 整除,而 $$$3$$$、$$$6$$$ 和 $$$12$$$ 可以被 $$$a_j = 3$$$ 整除,所以答案是“是”。