write a go solution for 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,ldotsa_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|)negcd(C_1,C_2,ldots,C_|C|) ^∗ ^∗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<=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,ldots,a_n (1<=a_i<=10^4).OutputFor each test case, first output textttYes if a solution exists or textttNo if no solution exists. You may print each character in either case, for example textttYES and textttyEs 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)=3ne1=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.. Output only the code with no comments, explanation, or additional text.