题目描述

You have an array $a$ of size $n - a_1,a_2,…a_n.$

You need to divide the n elements into $2$ sequences $B$ and $C$, satisfying the following conditions:

Each element belongs to exactly one sequence. Both sequences $B$ and $C$ contain at least one element. $gcd(B_1,B_2,…,B_{|B|})≠gcd(C_1,C_2,…,C_{|C|})$∗

*$gcd(x,y)$ denotes the greatest common divisor $(GCD)$ of integers $x$ and $y$.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1≤t≤500 )$. The description of the test cases follows.

The first line of each test case contains an integer $n (2≤n≤100).$

The second line of each test case contains $n$ integers $a_1,a_2,…,a_n (1≤a_i≤10^4).$

输出格式

For each test case, first output Yes if a solution exists or No

Only when there is a solution, output $n$ integers on the second line. The $i -th$ number should be either 1 or 2. 1 represents that the element belongs to sequence B and 2 represents that the element belongs to sequence C.

You should guarantee that 1 and 2 both appear at least once.

输入样例:

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