#P5074. [Lydsy1710月赛]小B的数字

[Lydsy1710月赛]小B的数字

小B的数字

题目描述

给定正整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n,判断是否存在序列 b1,b2,…,bnb_1,b_2,\ldots,b_n,满足:

  • 每个 bib_i 都是2的正整数次幂,即 2,4,8,…2,4,8,\ldots,不能为1。
  • 令 X=∏j=1nbjX=\prod_{j=1}^n b_j,对每个 1≤i≤n1\le i\le n,都有 X∣biaiX\mid b_i^{a_i}。

只需判断是否存在,不需要输出 bb。

输入格式

从标准输入读入。第一行一个正整数 TT,表示数据组数。

每组数据第一行一个正整数 nn,第二行 nn 个正整数 aia_i。

输出格式

每组数据向标准输出写出一行 YES 或 NO,表示是否存在满足条件的序列 bb。

样例输入

3
2
3 2
3
3 3 3
2
1 10

样例输出

YES
YES
NO

样例说明

第一组可取 b=(2,2)b=(2,2),X=4X=4,232^3 和 222^2 都是4的倍数。

第二组可取 b=(2,2,2)b=(2,2,2),满足条件。

第三组若存在 b=(α,β)b=(\alpha,\beta),由 αβ∣α\alpha\beta\mid\alpha 可知 β=1\beta=1,这不是2的正整数次幂,因此无解。

数据范围

30%的数据满足 n≤5,ai≤3n\le5,a_i\le3。

100%的数据满足 n≤105,ai≤10,T≤10n\le10^5,a_i\le10,T\le10。