Problem Statement

现在给出一个表达式，形如 $a_{1}/a_{2}/a_{3}/…/a_{n}$。

如果直接计算，就是一个个除过去，比如 $1/2/1/4 = 1/8$。

然而小$\text{A}$看到一个分数感觉很不舒服，希望通过添加一些括号使其变成一个整数。一种可行的办法是 $(1/2)/(1/4)=2$ 。

现在给出这个表达式，求问是否可以通过添加一些括号改变运算顺序使其成为一个整数。

Input

一个测试点中会有多个表达式。

第一行 $t$ ，表示表达式数量。

对于每个表达式，第一行是 $n$，第二行 $n$ 个数，第 $i$ 个数表示 $a_{i}$。

Output

输出 $t$ 行。

对于每个表达式，如果可以通过添加括号改变顺序使其变成整数，那么输出 Yes，否则输出 No。

Sample Input

1
2
3
4
5

2
4
1 2 1 4
5
6 5 7 9 12

Sample Output

1
2

Yes
No

Constraints

• 对于 $40%$ 的数据，$n \le 16$。
• 对于 $70%$ 的数据，$n \le 100$。
• 对于 $100%$ 的数据， $2 \le n \le 10000$，$1 \le t \le 100$，$1 \le a_{i}\le 2^{31}-1$。

Solving

注意到我们可以将原式变为 ：

$a_1$ $a_3$ $a_4$ … $a_n$ / $a_2$

变为此式后，加减括号对分子上的乘法不受影响，我们只需要判断上式的答案是否为整数即可，考虑分式的化简，即同时对分子和分母除以一个他们之间的约数，我们可以不断对上式化简，一旦能将$a_2$化简为1，则证明上式的答案一定是个整数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

ll gcd(int a,int b){return b==0?a:gcd(b,a%b);};
void solve()
{
    int n;
    cin >> n;
    int a[n+1];
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++)
    {
        if(i==2) continue;
        a[2] /= gcd(a[2],a[i]);
        if(a[2]==1)
        {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}