Taco Team Color Assignment

You are given T test cases. For each test case, you are given a single integer N representing the number of participants. Your task is to assign a team color (represented by a positive integer) to each participant such that no two adjacent participants have the same color. It turns out that using 2 colors is always sufficient, even if there is only one participant. In other words, for every valid index i (with 1 ≤ i < N), the assigned color must satisfy \(a_i \neq a_{i+1}\).

For each test case, output two lines: the first line should display the minimum number of different colors used (which will always be 2), and the second line should contain the assigned colors for all participants separated by a space.

Example:

Input:
2
3
5
Output:
2
1 2 1
2
1 2 1 2 1

</p>

inputFormat

The first line of input contains an integer T representing the number of test cases. Each of the following T lines contains a single integer N representing the number of participants for that test case.

Input Format:

T
N1
N2
... 
NT

outputFormat

For each test case, print two lines. The first line contains the integer 2 (the minimum number of colors needed). The second line contains N integers separated by a space representing the color assigned to each participant such that no two adjacent participants have the same color.

Output Format:

2
c1 c2 ... cN

## sample

1
1

2
1

</p>