【普及】相等

给了你一个长度为 $n$ 的正整数序列 $a_1, \cdots a_n$，你可以做以下两种操作任意次

• 选择正整数 $i, j, d$ 满足 $1 \le i < j \le n$ 且 $d | a_i, d | a_j$，然后将 $a_i \leftarrow \frac{a_i}{d}, a_j \leftarrow \frac{a_j}{d}$
• 选择正整数 $i, j, d$ 满足 $1 \le i < j \le n$，然后将 $a_i \leftarrow a_i \times d, a_j \leftarrow a_j \times d$

如果不理解上面的数学符号，可以这么理解这两种操作：

• 选择 $2$ 个数 $a_i$ 和 $a_j$，将它们同时除以某个数 $d$，需要满足 $a_i$ 和 $a_j$ 都是 $d$ 的倍数
• 选择 $2$ 个数 $a_i$ 和 $a_j$，将它们同时乘以某个数 $d$

判断通过若干次操作后，能否使 $a_1 = a_2 = \cdots = a_n$。

输入格式

第一行仅包含一个整数 $T(1 \le t \le 10^5)$，表示测试数据组数。每组数据的格式如下：

第一行，一个整数 $n(1 \le n \le 10^6)$，表示给定的序列长度。

第二行，$n$ 个整数 $a_1, \cdots a_n (1 \le a_i \le 5 \times 10^6)$，描述初始的序列。

保证所有测试数据中，$n$ 的和不超过 $2 \times 10^6$。

输出格式

对于每组测试数据：输出一行一个字符串表示答案

• 如果可以做到，输出 YES
• 如果不能做到，输出 NO

6
1
6
2
2 4
3
1 3 3
4
5 3 15 2
5
1 3 8 7 6
6
13 15 39 169 9 5

YES
NO
YES
NO
YES
YES

提示

【样例 1 解释】

• 对于第一组数据，由于 $n = 1$，已经满足所有数字相同，答案为 YES
• 对于第二组数据，容易发现无论如何操作，$a_1$ 都不可能与 $a_2$ 相等
• 对于第三组数据，可以选取 $i = 2，j = 3，d = 3$ 并进行第一种操作，使得原序列变为 $[1, 1, 1]$，此时所有数字均相同，因此输出 YES

【数据范围】

• $1 \le T \le 10^5, 1 \le n \le 10^6$
• $1 \le a_i \le 5 \times 10^6$
• 保证所有测试数据中，$n$ 的和不超过 $2 \times 10^6$

来源