1991D - Prime XOR Coloring - CodeForces Solution

n= int(input())
for i in range(n):
    m= int(input())
        ans = [0]*m
    if m==1:
        print(1)
        ans =[1]
        print(*ans,sep=" ")
    elif m==2:
        print(2)
        ans =[1,2]
        print(*ans,sep=" ")
    elif m==3:
        print(2)
        ans =[1,2,2]
        print(*ans,sep=" ")
    elif m==4:
        print(3)
        ans =[1,2,2,3]
        print(*ans,sep=" ")
    elif m==5:
        print(3)
        ans =[1,2,2,3,3]
        print(*ans,sep=" ")
    elif m==6:
        print(4)
        ans =[1,2,2,3,3,4]
        print(*ans,sep=" ")
    else:
        print(4)
        for j in range(m):
            ans[j] = j%4 +1 
        print(*ans, sep =" ")