Colorful Points

In this problem, all points are integer points located on the number axis.

There is a set of colorful points P, where point P_k has color k and is located at k,1<=k<=n. Colors of points in set P are pairwise different.

Now, we want to color another set of points Q, where point Q_k is located at –n+k, 1<=k<=n. Every point in set Q must be colored with one of colors 1, 2, …, n, and all colors must be used at least once. After we finish coloring all points in set Q, we will shift them right by the speed of one unit per second, which means that point Q₁ changes its location to –n+2, point Q₂ changes its location to –n+3, …, point Q_n changes its location to 1 in the 1^st second; and point Q₁ changes its location to –n+3, point Q₂ changes its location to –n+4, …, point Q_n changes its location to 2 in the 2^nd second and so on. We will end the process after 2*n seconds (Q₁ -> n+1, Q₂ -> n+2, Q_n -> 2*n).

We define two parameters here. Let A_k represent the number of different pairs of points coincide in the k-th second. A pair of points coincides in the k-th second means that a point from set Q has the same location with that of a point from set P in the k-th second, such as point Q_n changes its location to 1 which is the same as that of point P₁ in the 1^st second, so the pair (Q_n, P₁) is a pair of points coincides in the 1^st second, and pairs (Q_n-1, P₁) and (Q_n, P₂) are two different pairs of points coincide in the 2^nd second and so on. Let B_k represent the number of pairs of points which have the same color among all the pairs of points coincide in the k-th second. To help you understand A_k and B_k better, we give an example below:

e.g. Let n = 3, and we color point Q₃ with color 2, pointQ₂ with color 3, point Q₁ with color 1. In the 1^st second, (Q₃, P₁) is the only pair of points coincide, but the color of point Q₃ is different from that of point P₁, so A₁ = 1 and B₁ = 0; In the 2^nd second, (Q₃, P₂) and (Q₂, P₁) are the only two pairs of points coincide, and point Q₃ and point P₂ have a same color while point Q₂ and point P₁ have a different color, so A₂ = 2 and B₂ = 1; In the 3^rd second, there are three pairs of points coincide, which are (Q₁, P₁) with a same color and (Q₂, P₂), (Q₃, P₃) with a different color, so A₃ = 3 and B₃ = 1; In the 4^th second, A₄ = 2 and B₄ = 1; In the 5^th second, A₅ = 1 and B₅ = 0; In the 6^th second, A₆ = 0 and B₆ = 0.

We define another parameter C, where C=max{A_k - B_k}, 1<=k<=2*n. If you have finished coloring all the points in set Q, parameter C is easy to be calculated, and different ways of coloring may lead to different Cs. Among all the Cs, there is a minimum one. In this problem, your job is to calculate the minimum C and give a way of coloring which leads to the minimum C.

At the beginning, there is an integer T indicating the total number of test cases.
Every test case occupies a single line with only one integer n.
　　T <= 100;
　　1 <= n <= 100000;
Most ns are less than 1000.

For every test case, print “Case #k: ” firstly, where k indicates the index of the test case and begins from 1. Then output the minimum C. Finally give a way of coloring which leads to the minimum C in the next line (give the color of points in the order of Q₁, Q₂, …, Q_n and separate them with a single blank), and each way leads to minimum C will be correct. See sample for more details.

4
1
2
3
4

Case #1: 0
1
Case #2: 1
1 2
Case #3: 2
1 2 3
Case #4: 2
1 2 4 3

2012 Multi-University Training Contest 10