Problem Description

The tram network in a certain city can be pictured as $n$ tram stations evenly spaced around a circle. The tram stations are labeled with the positive integers from $1$ to $n$ in clockwise order. There is exactly one track between every two stations, and trams always travel clockwise.

A ride of length $l$ ($1 \le l \le n-1$) takes you from your current station to the station $l$ stops further along in the clockwise direction.

The Tram Administration sells a separate ticket for each ride length. As part of a promotional campaign, they decided to color each type of ticket and offer a free monthly pass to any person who:

• returns, through a sequence of rides, to the station they started from, and
• uses tickets of pairwise distinct colors on that trip.

The bosses at the Administration liked the idea of coloring tickets as a promotional strategy, but not the idea of someone riding their trams for free, so they will agree to the coloring only if no person can win the free monthly pass.

Of course, all tickets could be the same color, but then it would be immediately obvious to the public that winning the free monthly pass is impossible. Not bothered by concerns about false advertising, the bosses ask you for a coloring that uses as many colors as possible!

Input Format

The first line contains a positive integer $t$ ($1 \le t \le 1000$), the number of scenarios.

Each of the following $t$ lines contains a positive integer $n$ ($2 \le n \le 2\cdot 10^5$), the number of tram stations in the network.

The sum of $n$ over all scenarios will not exceed $2\cdot 10^5$.

Output Format

For each of the $t$ scenarios, in order, output two lines.

In the first line, output a positive integer $k$, the number of colors used to color the tickets.

In the second line, output $n-1$ numbers $c_1,\ldots,c_{n-1}$ separated by spaces, where $c_i$ is the color of the ride of length $i$. Each color must be a positive integer from the set $\{1,2,\ldots,k\}$, and every number in that set must appear at least once.

1
3

1
1 1

2
4
5

2
2 1 2
2
1 2 2 1

1
6

2
2 1 2 1 2

Hint

Scoring

In each scenario, let $k$ be the number of colors output by your solution, and let $k_{\mathrm{opt}}$ be the largest possible number of colors. If the coloring output in any scenario does not satisfy the conditions of the problem, the solution scores 0 points on that test case.

Otherwise, for each scenario we compute the ratio

$$r=\begin{cases} 1, & \text{if } k_{\mathrm{opt}}=1 \text{ and } k=1,\\ \dfrac{k-1}{k_{\mathrm{opt}}-1}, & \text{if } k_{\mathrm{opt}}>1. \end{cases}$$

The fraction of points earned on a test case is the minimum ratio $r$ over all scenarios in that test case. The number of points earned on a subtask is the subtask's point value multiplied by the minimum such fraction over all test cases in that subtask.

Subtask	Points	Constraints
1	20	$n \le 12$.
2	10	$n$ is a prime number.
3	15	$n$ is a power of $2$.
4	65	No additional constraints.