你有一个大小为 $$$n$$$ 的数组 $$$a$$$ — $$$a_1, a_2, \ldots a_n$$$。
需要将$$$n$$$元素划分为$$$2$$$序列$$$B$$$和$$$C$$$,满足以下条件:
- 每个元素都属于一个序列。
- 序列 $$$B$$$ 和 $$$C$$$ 都至少包含一个元素。
- $$$\gcd$$$ $$$(B_1, B_2, \ldots, B_{|B|}) \ne \gcd(C_1, C_2, \ldots, C_{|C|})$$$ $$$^{\text{*}}$$$
$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^4$$$)。
输出
对于每个测试用例,如果存在解决方案,则首先输出 $$$\texttt{Yes}$$$;如果不存在解决方案,则首先输出 $$$\texttt{No}$$$。您可以在任一情况下打印每个字符,例如 $$$\texttt{YES}$$$ 和 $$$\texttt{yEs}$$$ 也将被接受。
只有当有解时,才在第二行输出$$$n$$$个整数。第 $$$i$$$ 个数字应该是 $$$1$$$ 或 $$$2$$$。 $$$1$$$表示该元素属于序列$$$B$$$,$$$2$$$表示该元素属于序列$$$C$$$。
您应该保证 $$$1$$$ 和 $$$2$$$ 都至少出现一次。
示例
输入复制
341 20 51 945 5 5 531 2 2
输出复制
Yes 2 2 1 1 No Yes 1 2 2
注意
在第一个测试用例中,$$$B = [51, 9]$$$ 和 $$$C = [1, 20]$$$。您可以验证 $$$\gcd(B_1, B_2) = 3 \ne 1 = \gcd(C_1, C_2)$$$。
在第二个测试用例中,不可能找到解决方案。例如,假设您将前 $$$3$$$ 元素分配给数组 $$$B$$$,然后将最后一个元素分配给数组 $$$C$$$。您有 $$$B = [5, 5, 5]$$$ 和 $$$C = [5]$$$,但是 $$$\gcd(B_1, B_2, B_3) = 5 = \gcd(C_1)$$$。因此它是无效的。