题目描述

小蓝和朋友小桥正在玩一个关于正整数的游戏。

初始时，桌面上有 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。小蓝先手，两人轮流操作。

一次操作需要选择当前桌面上的一个数 $x$，并将它修改为一个更小的正整数 $y$。这个修改合法当且仅当 $1 \le y < x$，且 $x$ 与 $y$ 不互质。

“不互质”指两个正整数的最大公约数大于 $1$，即 $\gcd(x, y) > 1$。例如，对于数字 $8$，可以将它修改为 $2, 4, 6$；对于数字 $15$，可以将它修改为 $3, 5, 6, 9, 10, 12$。数字 $1$ 和所有质数均无法被修改，因为它们不存在满足条件的更小正整数 $y$。

当轮到某名玩家操作时，如果他无法做出任何合法操作，则该玩家输掉游戏。

已知小蓝和小桥都会采取最优策略，现在请你判断，在给定的初始局面下，小蓝是否必胜。

输入格式

本题包含多组数据。

第一行包含一个正整数 $T$, 表示数据组数。

接下来依次输入 $T$ 组数据。每组数据包含两行：

• 第一行包含一个正整数 $n$，表示初始数字个数；
• 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示游戏的初始局面。

输出格式

对于每组数据输出一行。

若小蓝必胜，输出 Yes；否则输出 No。

2
3
1 3 100
2
100000 100000

Yes
No

提示

【样例说明】

对于第一组数据，小蓝可以将 $100$ 修改为 $2$。此后 $1, 3, 2$ 都无法继续被合法修改，小桥无合法操作，因此小蓝必胜。

对于第二组数据，两个数相同。无论小蓝如何修改其中一个数，小桥都可以对另一个数进行相同修改，最终由小蓝面对无合法操作的局面，因此小桥必胜。

【评测用例规模与约定】

对于 $40\%$ 的评测用例，$1 \le n \le 10$, $1 \le a_i \le 3000$;

对于 $80\%$ 的评测用例，$1 \le n \le 100$, $1 \le a_i \le 20000$;

对于所有评测用例，$1 \le T \le 200$, $1 \le n \le 1000$, $1 \le a_i \le 300000$, 且所有数据的 $n$ 之和不超 $100000$。