题目描述

给你一个长为 $n$ 的数组 $a=(a_1,a_2,\cdots,a_n)$。

你需要把它分成两个子序列 $B$ 和 $C$，使得：

• $a$ 中的每个元素都属于两个子序列中的一个。
• 两个子序列都至少包含一个元素。
• 两个子序列的最大公因数不相等。

请判断是否有解，如果有解，请给出方案。

最大公因数的定义——维基百科

输入格式

多组数据，第一行一个整数，为数据组数 $t(1\le t\le 500)$。

对于每组数据：第一行一个整数，表示 $n(2\le n\le 100)$。

第二行 $n$ 个整数 $a_1,a_2,\cdots a_n(1\le a_i\le 10^4)$。

输出格式

对于每组数据，如果有解，第一行输出 Yes，否则第一行输出 No。大小写不敏感。

如果有解，你需要输出第二行表示一种方案，为空格隔开的 $n$ 个数字，第 $i$ 个数字为 $1$ 表示 $a_i$ 被划分到 $B$ 中，为 $2$ 则表示 $a_i$ 被划分到 $C$ 中。你需要保证 $1$ 和 $2$ 都至少出现一次。

如果有多种合法方案，输出任意一种均可。

说明/提示

第一组数据的输出中，$B=(51,9),C=(1,20)$。$\gcd(B_1,B_2)=3\ne1=\gcd(C_1,C_2)$。

对于第二组数据，没有合法的方案。存在方案 $B=(5,5,5),C=(5)$，但是 $\gcd(B_1,B_2,B_3)=5=\gcd(C_1)$，所以此方案非法。

By chenxi2009

样例

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