A. LRC and VIPtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output You have an array $$$a$$$ of size $$$n$$$ — $$$a_1, a_2, \ldots 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, \ldots, B_{|B|}) \ne \gcd(C_1, C_2, \ldots, C_{|C|})$$$ $$$^{\text{∗}}$$$ $$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$. InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows. The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 100$$$).The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^4$$$).OutputFor each test case, first output $$$\texttt{Yes}$$$ if a solution exists or $$$\texttt{No}$$$ if no solution exists. You may print each character in either case, for example $$$\texttt{YES}$$$ and $$$\texttt{yEs}$$$ will also be accepted.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.ExampleInput341 20 51 945 5 5 531 2 2OutputYes
2 2 1 1
No
Yes
1 2 2
NoteIn the first test case, $$$B = [51, 9]$$$ and $$$C = [1, 20]$$$. You can verify $$$\gcd(B_1, B_2) = 3 \ne 1 = \gcd(C_1, C_2)$$$.In the second test case, it is impossible to find a solution. For example, suppose you distributed the first $$$3$$$ elements to array $$$B$$$ and then the last element to array $$$C$$$. You have $$$B = [5, 5, 5]$$$ and $$$C = [5]$$$, but $$$\gcd(B_1, B_2, B_3) = 5 = \gcd(C_1)$$$. Hence it is invalid.