每次测试时间限制：1 秒
每次测试内存限制：256 兆字节

题目描述

你有一个大小为 $n$ 的数组 $a$，即 $a_1, a_2, \dots, a_n$。

需要将 $n$ 个元素划分成两个序列 $B$ 和 $C$，满足以下条件：

• 每个元素恰好属于一个序列。
• 两个序列 $B$ 和 $C$ 都至少包含一个元素。
• $\gcd(B_1, B_2, \dots, B_{|B|}) \neq \gcd(C_1, C_2, \dots, C_{|C|})$。

这里 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

输入格式

每个测试包含多个测试用例。
第一行包含一个整数 $t$（$1 \leq t \leq 500$），表示测试用例数量。
接下来每个测试用例的格式如下：

• 第一行包含一个整数 $n$（$2 \leq n \leq 100$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^4$）。

输出格式

对于每个测试用例：

• 第一行输出 Yes 如果存在解，否则输出 No。大小写不敏感，例如 YES、yEs 也可接受。
• 仅当存在解时，再在第二行输出 $n$ 个整数，第 $i$ 个数为 $1$ 或 $2$。
  $1$ 表示该元素属于序列 $B$，$2$ 表示属于序列 $C$。
  必须保证 $1$ 和 $2$ 都至少出现一次。

示例

输入

3
4
1 20 51 9
4
5 5 5 5
3
1 2 2

输出

Yes
2 2 1 1
No
Yes
1 2 2

样例解释

在第一个测试用例中：
$B = [51, 9]$，$C = [1, 20]$。可以验证 $\gcd(B_1, B_2) = 3 \neq 1 = \gcd(C_1, C_2)$。

在第二个测试用例中，不存在解。例如，若将前 $3$ 个元素分给 $B$，最后一个给 $C$，则 $B = [5,5,5]$，$C = [5]$，$\gcd(B) = 5 = \gcd(C)$，不符合要求。

在第三个测试用例中，存在解。