由于题目的操作基于每个数的公因数,我们考虑将每个数质因分解进行考虑。
例如题目给的例子:
18 = 2 * 3 * 3
18 = 2 * 3 * 3
小红喜欢全都是1的数组,他有一个大小为n的数组a。
小红每次操作可以选择一对i,j(i=j),然后使得ai,aj同时除以这两个数字的任意一个公因数,小红想知道他是否可以在若干次操作后将数组变成全都是1的数组。
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤2×105)代表数据组数,每组测试数据如下:
第一行输入一个整数n(1≤n≤2×105)表示数组长度。
第二行输入n个整数表示数组a1,a2,...,an(1≤ai≤2×105)。
除此之外,保证所有的n之和不超过2×105
对于每次询问,如果可以把数组变成全都是1的数组,则输出”YES“,否则输出”NO“。
输入
2
3
18 18 36
3
3 2 1
输出
YES
NO
说明
对于第一组测试数据: