题目描述

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

1. 选择正整数 $i, j$，满足 $1 \leq i < j \leq n$ 且存在 $d$ 使得 $d | a_i$ 和 $d | a_j$，然后将 $a_i \leftarrow \frac{a_i}{d}$，$a_j \leftarrow \frac{a_j}{d}$；
2. 选择正整数 $i, j$，满足 $1 \leq i < j \leq n$，然后将 $a_i \leftarrow a_i \times d$，$a_j \leftarrow a_j \times d$，其中 $d$ 是任意正整数。

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

输入格式

本题中有多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试数据组数。每组测试数据的格式如下：

第一行：一个整数 $n$（$1 \leq n \leq 10^6$），表示序列长度。

第二行：$n$ 个整数 $a_1, \ldots, a_n$（$1 \leq a_i \leq 5 \cdot 10^6$），描述初始序列。

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

输出格式

对于每组测试数据，输出一行一个字符串表示答案。输出 YES 当且仅当可以通过若干次操作使得序列中所有元素相等；否则输出 NO。

你可以以任意大小写形式输出答案。例如，yEs、yes、Yes、YES 都被认作是肯定的回答。

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。