题目描述

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

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

输入格式

本题有多组测试数据。

输入第一行一个正整数 $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$。

输出格式

对于每组数据：

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

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

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

YES
YES
NO
NO
YES
NO
YES