The round carousel consists of $n$ figures of animals. Figures are numbered from $1$ to $n$ in order of the carousel moving. Thus, after the $n$-th figure the figure with the number $1$ follows. Each figure has its own type — the type of the animal corresponding to this figure (the horse, the tiger and so on). The type of animal of the $i$-th figure equals $t_i$. [Image] The example of the carousel for $n=9$ and $t=[5, 5, 1, 15, 1, 5, 5, 1, 1]$. 

You want to color each figure in one of the colors. You think that it's boring if the carousel contains two different figures (with the distinct types of animals) going one right after another and colored in the same color.

Your task is to color the figures in such a way that the number of distinct colors used is the minimum possible and there are no figures of the different types going one right after another and colored in the same color. If you use exactly $k$ distinct colors, then the colors of figures should be denoted with integers from $1$ to $k$.


-----Input-----

The input contains one or more test cases.

The first line contains one integer $q$ ($1 \le q \le 10^4$) — the number of test cases in the test. Then $q$ test cases follow. One test case is given on two lines.

The first line of the test case contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of figures in the carousel. Figures are numbered from $1$ to $n$ in order of carousel moving. Assume that after the $n$-th figure the figure $1$ goes.

The second line of the test case contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 2 \cdot 10^5$), where $t_i$ is the type of the animal of the $i$-th figure.

The sum of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

Print $q$ answers, for each test case print two lines.

In the first line print one integer $k$ — the minimum possible number of distinct colors of figures.

In the second line print $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le k$), where $c_i$ is the color of the $i$-th figure. If there are several answers, you can print any.


-----Example-----
Input
4
5
1 2 1 2 2
6
1 2 2 1 2 2
5
1 2 1 2 3
3
10 10 10

Output
2
1 2 1 2 2
2
2 1 2 1 2 1
3
2 3 2 3 1
1
1 1 1

Difficulty: introductory

Starter code:

Solutions:
import sys
input = lambda: sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(a) for a in input().split()]
    
    if max(A) == min(A):
        print(1)
        print(*([1] * N))
    elif N % 2 == 0:
        print(2)
        print(*([1, 2] * (N // 2)))
    else:
        for i in range(N):
            if A[i-1] == A[i]:
                print(2)
                print(*(([1, 2] * N)[:i][::-1] + ([1, 2] * N)[:N-i]))
                break
        else:
            print(3)
            print(*([3] + [1, 2] * (N // 2)))



t = int(input())
for case_num in range(t):
    n = int(input())
    a = list(map(int, input().split(' ')))
    color = [1] * n
    if len(set(a)) == 1:
        print(1)
        print(' '.join(map(str, color)))
    else:
        one = [False] * n
        two = [False] * n
        one[0] = True
        for i in range(n - 1):
            if a[i] == a[i + 1]:
                color[i + 1] = color[i]
            else:
                color[i + 1] = 3 - color[i]
        if a[0] == a[n - 1] or color[0] != color[n - 1]:
            print(2)
            print(' '.join(map(str, color)))
        else:
            backup = color.copy()
            color[n - 1] = 2
            i = n - 2
            while i >= 0 and a[i] != a[i + 1] and color[i] == color[i + 1]:
                color[i] = 3 - color[i + 1]
                i -= 1
            if color[0] == 1:
                print(2)
                print(' '.join(map(str, color)))
            else:
                backup[n - 1] = 3
                print(3)
                print(' '.join(map(str, backup)))


q = int(input())

for _ in range(q):
    n = int(input())
    
    t = list(map(int, input().split()))
    
    t_set = set(t)
    
    if len(t_set) == 1:
        print(1)
        print(*([1] * n))
        continue
    
    if n%2==0:
        print(2)
        print(*([1,2]*(n//2)))
        continue
        
    found = -1
    for i, (t1, t2) in enumerate(zip(t, t[1:]+[t[0]])):
        if t1==t2:
            found = (i+1)%n
    if found >= 0:
        print(2)
        r = []
        one = True
        for i in range(n):
            if i==found:
                one = not one
            if one:
                r += [1]
            else:
                r += [2]
            one = not one
        print(*r)
        continue
    
    print(3)
    r = [1, 2] * (n//2) + [3]
    print(*r) 
    
            



q = int(input())

for loop in range(q):

    n = int(input())

    t = list(map(int,input().split()))

    dic = {}
    for i in t:
        dic[i] = 1

    if len(dic) == 1:
        k = 1
        ans = [1] * n
    elif n % 2 == 0:

        k = 2
        ans = []
        for i in range(n):
            if i % 2 == 0:
                ans.append(1)
            else:
                ans.append(2)

    else:

        flag = 0
        ans = []

        for i in range(n):

            if flag == 0 and t[i-1] == t[i]:
                flag = 1

            ans.append( (i+flag) % 2 )

        if flag == 0:
            ans[-1] = 2
            k = 3
        else:
            k = 2

        for i in range(n):
            ans[i] += 1

    print (k)
    print(*ans)


from itertools import groupby


def go():
    # n,k = map(int,input().split()
    n = int(input())
    x = list(map(int, input().split()))

    if all(xx == x[0] for xx in x):
        return '1\n' + ' '.join(['1'] * (n))
    if n % 2 == 0:
        return '2\n' + ' '.join(['1', '2'] * (n // 2))

    prev=x[-1]
    done=False
    ans=[]
    cur=0
    for xx in x:
        if prev==xx and not done:
            done=True
        else:
            cur=(cur+1)%2
        ans.append(str(cur + 1))
        prev=xx

    if not done:
        ans[0]='3'
        v='3'
    else:
        v='2'

    return v +'\n' + ' '.join(ans)


# x,s = map(int,input().split())
t = int(input())
# t=1
ans = []
for _ in range(t):
    # go()
    ans.append(str(go()))

print('\n'.join(ans))


q = int(input())
for test_case in range(q):
    n = int(input())
    t = input().split()
    if n==1:
        print(1)
        print(1)
        continue
    t_0 = t[0]
    all_same = True
    any_adj_same = False
    adj_same_index = -1
    for i in range(0,len(t)):
        animal = t[i]
        if animal!=t_0:
            all_same = False
        if animal==t[(i+1)%n]:
            any_adj_same = True
            adj_same_index = i

    if all_same:
        print(1)
        output = ""
        for i in range(n):
            output+=" 1"
        output = output[1:]
        print(output)
        continue

    if n%2==0:
        print(2)
        output = ""
        for i in range(n):
            output+= (" 1" if i%2 == 0 else " 2")
        output = output[1:]
        print(output)
        continue
    if any_adj_same:
        print(2)
        output = ""
        for i in range(n):
            if i>adj_same_index:
                output+= (" 2" if i%2 == 0 else " 1")
            else:
                output+= (" 1" if i%2 == 0 else " 2")
        output = output[1:]
        print(output)
        continue
    else:
        print(3)
        output = ""
        for i in range(n-1):
            output+= ("1 " if i%2 == 0 else "2 ")
        output += "3"
        print(output)
        continue


t=int(input())
for foo in range(t):
    n=int(input())
    t=list(map(int,input().split()))
    same=1
    pair=0
    for i in range(n):
        if t[i]==t[i-1]:
            pair=1
        else:
            same=0
    if same==1:
        print(1)
        print(*([1]*n))
    else:
        if n%2==0:
            print(2)
            print(*([1,2]*(n//2)))
        else:
            if pair==1:
                print(2)
                s=[1]*n
                p=0
                for i in range(n-1):
                    if p==1 or t[i]!=t[i-1]:
                        s[i]=3-s[i-1]
                    else:
                        p=1
                        s[i]=s[i-1]
                print(*s)
            if pair==0:
                print(3)
                print(*([1,2]*(n//2)),3)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(item) for item in input().split()]
    kind = len(set(a))
    # Single animal
    if kind == 1:
        ans = [1] * n
        print(1)
        print(*ans)
        continue
    # Has sequence
    a.append(a[0])
    l = 0
    has_sequence = False
    for i, (a1, a2) in enumerate(zip(a, a[1:])):
        if a1 == a2:
            l = i
            has_sequence = True
            break
    # All different
    if not has_sequence:
        if n % 2 == 0:
            ans = [1, 2] * (n // 2)
            print(2)
            print(*ans)
        else:
            ans = [1, 2] * (n // 2) + [3]
            print(3)
            print(*ans)
        continue
    if n % 2 == 0:
        ans = [1, 2] * (n // 2)
        print(2)
        print(*ans)
    else:
        ans = [1, 2] * (n // 2)
        if l == n - 1:
            ans.append(ans[0])
        else:
            ans.insert(l, ans[l])
        print(2)
        print(*ans)

def changed(colors,types,n):
    index = -1
    for i in range(n-1,0,-1):
        if types[i] == types[i-1]:
            index = i-1
            break

    if index == -1:
        colors[n-1] = 3
        return True

    for i in range(index+1,n):
        if colors[i-1] == 1:
            colors[i] = 2
        else:
            colors[i] = 1

    return False
    

def solve(types,n,ans):
    colors = []
    colors.append(1)
    k = 1
    for i in range(1,n):
        if types[i] != types[i-1]:
            k += 1
            if colors[-1] == 1:
                colors.append(2)
            else:
                colors.append(1)
        else:
            colors.append(colors[-1])

    k = min(k,2)
    if colors[n-1] == colors[0] and types[n-1] != types[0]:
        if changed(colors,types,n):
            k += 1

    ans.append([k])
    ans.append(colors)
            

def main():
    ans = []
    q = int(input())
    for i in range(q):
        n = int(input())
        types = list(map(int,input().split()))
        solve(types,n,ans)

    for i in ans:
        for j in i:
            print(j,end = ' ')

        print()

main()


import sys
input = sys.stdin.readline

t=int(input())

for tests in range(t):
    n=int(input())
    A=list(map(int,input().split()))

    ANS=[-1]*n
    ANS[0]=1

    if min(A)==max(A):
        print(1)
        print(*[1]*n)
        continue

    if n%2==1:
        flag=0
    else:
        flag=1
        
    for i in range(1,n):
        if flag==0:
            if A[i]==A[i-1]:
                ANS[i]=ANS[i-1]
                flag=1
            else:
                ANS[i]=3-ANS[i-1]
        else:
            ANS[i]=3-ANS[i-1]

    if flag==0 and A[i]!=A[0]:
        ANS[n-1]=3

    print(max(ANS))
    print(*ANS)


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    ans=[1]*(n)
    f=1
    ind=0
    if a[0]==a[1]:
        ind=1
    for i in range(1,n):
        if a[i]==a[i-1]:
            ans[i]=ans[i-1]
        else:
            ans[i]=3-ans[i-1]
            f=2
        if a[i]==a[(i+1)%n]:
            ind=(i+1)%n
        
    if a[0]!=a[-1] and ans[-1]==ans[0]:
        ans[-1]=3
        f=3
    
    # print(ind)
    
    if f==3 and ind:
        for i in range(ind,n):
            ans[i]=3-ans[i]
        ans[-1]=3-ans[0]    
            
    
    print(len(set(ans)))    
    
    
    # if f:
    #     print(3)
        
    # else:
    #     print(2)
    print(*ans)    

def pos(ls):
    for i in range(-1, len(ls)-1):
        if ls[i] == ls[i+1]:
            return i
    return -2
for i in range(int(input())):
    n = int(input())
    lst = list(map(int, input().split()))
    if len(set(lst)) == 1:
        print(1)
        lll = [1] * n
        print(*lll)
    else:
        if n % 2 == 0:
            lll = [1, 2] * (n//2)
            print(2)
            print(*lll)
        else:
            k = pos(lst)
            if k != -2:
                lll = [1, 2] * (n // 2)
                if k == -1:
                    print(2)
                    print(*lll, 1)
                else:
                    if lll[k] == 1:
                        lll[k] = '1 1'
                    else:
                        lll[k] = '2 2'
                    print(2)
                    print(*lll)
            else:
                print(3)
                lll = [1, 2] * (n // 2)
                print(*lll, 3)

for tc in range(int(input())):
    n = int(input())
    ls = list(map(int, input().split()))
    if len(set(ls)) == 1:
        print(1)
        print(' '.join(['1' for _ in range(n)]))
    else:
        solo = True
        ngroups = 0
        for i in range(n):
            if ls[i] == ls[i-1]:
                solo = False
            else:
                ngroups += 1

        shuffle = 1 if (ngroups%2 and not solo) else 0
            
        i = 0
        while ls[i] == ls[i-1]:
            i += 1
        res = [None for _ in range(n)]
        st = 1
        for j in range(n):
            if shuffle and ls[i] == ls[i-1]:
                st = 3-st
                shuffle = 0
            res[i] = st
            i = (i+1) % n
            if ls[i] != ls[i-1]:
                st = 3-st
            
        #print(res, st)
        if st == 2:
            i = (i-1) % n
            res[i] = 3
            while ls[(i-1) % n] == ls[i]:
                i = (i-1) % n
                res[i] = 3

        print(max(res))
        print(' '.join(map(str, res)))


for nt in range(int(input())):
	n=int(input())
	l=list(map(int,input().split()))
	s=list(set(l))
	s.sort()
	if len(s)==1:
		print (1)
		print (*([1]*n))
	elif len(s)==2:
		print (2)
		a=s[0]
		b=s[1]
		ans=[]
		for i in l:
			if i==a:
				ans.append(1)
			else:
				ans.append(2)
		print (*ans)
	else:
		ans=[1]
		for i in range(1,n):
			if i==n-1:
				if l[i]==l[i-1] and l[0]==l[i]:
					ans.append(ans[-1])
				elif l[i]==l[i-1] and l[i]!=l[0]:
					ans.append((ans[0]%2)+1)
				else:
					temp=(ans[-1]%2)+1
					if l[i]==l[0]:
						ans.append(temp)
					else:
						if temp==ans[0]:
							ans.append(3)
						else:
							ans.append(temp)
				continue
			if l[i]==l[i-1]:
				ans.append(ans[-1])
			else:
				ans.append((ans[-1]%2)+1)
		x=(len(set(ans)))
		if x==2:
			print (2)
			print (*ans)
			continue
		find=0
		for i in range(n-1,0,-1):
			if l[i]==l[i-1]:
				index=i
				prev=ans[i-1]
				find=1
				break
		if not find:
			print (3)
			print (*ans)
		else:
			for i in range(index,n):
				ans[i]=(ans[i-1]%2)+1
			print (2)
			print (*ans)

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    if len(set(a)) == 1:
        print(1)
        print(*([1]*n))
    elif n % 2 == 0:
        print(2)
        print(*([1, 2] * (n // 2)))
    else:
        flag = 1
        v = 0
        ans = [1]*n
        for i in range(1, n):
            if flag and a[i-1] == a[i]:
                flag = 0
            else:
                v ^= 1
            ans[i] = v+1

        if flag and a[0] != a[-1]:
            ans[-1] = 3
            print(3)
            print(*ans)
        else:
            print(2)
            print(*ans)


t = int(input())
while(t):
    t -= 1
    n = int(input())
    a = list(map(int, input().split()))
    if(len(set(a)) == 1):
        print(1)
        print("1 "*n)
    elif(n % 2 == 0):
        print(2)
        print("1 2 " * (n // 2))
    else:
        ans = [1]
        en = 1
        colour = 2
        for i in range(1, n):
            if(en and a[i] == a[i-1]):
                colour = 3 - colour
                en = 0
            ans.append(colour)
            colour = 3 - colour
        if(a[-1] != a[0] and ans[-1] == 1):
            ans[-1] = 3
        print(max(ans))
        print(*ans)