F. 交换余生
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定一个长为 $$$n$$$ 的序列 $$$a$$$。判断是否存在序列 $$$b$$$ 满足：

  • $$$S(a)=S(b)$$$，其中 $$$S(a)$$$、$$$S(b)$$$ 分别表示由序列 $$$a$$$ 和序列 $$$b$$$ 中所有元素构成的可重集；
  • 不存在 $$$1 \le i \lt n$$$ 满足 $$$\gcd(b_1,\cdots,b_i) = \gcd(b_{i+1},\cdots,b_n)$$$。
Input

本题有多组测试数据。

输入第一行一个正整数 $$$t$$$（$$$1 \le t \le 10$$$），表示数据组数。

每组数据中：

第一行一个正整数 $$$n$$$（$$$2 \le n \le 2 \times 10^5$$$），表示序列 $$$a$$$ 的长度。

第二行 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1 \le a_i \le 10^{12}$$$），表示序列 $$$a$$$。

保证 $$$\sum n \le 2 \times 10^5$$$。

Output

对于每组数据：

若存在序列 $$$b$$$ 满足条件，输出一行 "YES"，否则输出一行 "NO"。

你可以以任意大小写形式输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被视为正确回答。

Example
Input
7
4
6 12 24 15
5
2 4 3 9 6
6
2 3 5 4 9 25
4
7 7 14 21
2
10 20
3
6 6 6
5
14 21 22 33 17
Output
YES
YES
NO
NO
YES
NO
YES