题目描述

给定一个长度为 $n$ 的正整数序列 $a$。请判断是否可以将 $a$ 重新排列，使得存在一个整数 $i$（$1 \le i < n$）满足以下等式：

$$\min([a_1, a_2, \dots, a_i]) = \gcd([a_{i+1}, a_{i+2}, \dots, a_n])$$

在这里，$\gcd(c)$ 表示序列 $c$ 中所有元素的最大公约数，即能同时整除序列 $c$ 中所有元素的最大正整数。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 序列的长度。
• 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{18}$）—— 序列的元素。

输出格式

对于每个测试用例，如果可以通过重新排列满足条件，输出 Yes；否则输出 No。

样例输入 1

7
2
1 1
2
1 2
3
2 2 3
3
2 3 4
5
4 5 6 9 3
3
998244359987710471 99824435698771045 1000000007
6
1 1 4 5 1 4

样例输出 1

Yes
No
Yes
No
Yes
Yes
Yes

说明

样例解释

• 在第一个测试用例中，将 $a$ 排列为 $[1, 1]$ 并令 $i=1$，此时 $\min([1]) = \gcd([1])$ 成立。
• 在第二个测试用例中，可以证明无论如何排列都无法满足条件。
• 在第三个测试用例中，将 $a$ 排列为 $[3, 2, 2]$ 并令 $i=2$，此时 $\min([3, 2]) = \gcd([2])$ 成立。
• 在第五个测试用例中，将 $a$ 排列为 $[3, 4, 5, 6, 9]$ 并令 $i=3$，此时 $\min([3, 4, 5]) = \gcd([6, 9])$ 成立（两边均为 $3$）。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $2 \le n \le 10^5$，$1 \le a_i \le 10^{18}$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $10^5$。
• 保证所有的输入数值均为整数。