High School Programming League Problems Archive

You might be aware of the Ulam spiral. Your task in this problem is to print a finite Ulam-like spiral of integers but starting with 1 at the upper left corner (please consult the example below).

Input

You are given one integer t, denoting the number of testcases (t <= 100). In each of the following t lines one positive integer n ( n <= 200) - the requested size of the spiral.

Output

For each of the test cases output the requested spiral. Separate succesive cases by an empty line.

Example

Input:
4
2
4
1
5


Output:
 1  2 
 4  3 

 1  2  3  4 
12 13 14  5 
11 16 15  6 
10  9  8  7 

 1 

 1  2  3  4  5 
16 17 18 19  6 
15 24 25 20  7 
14 23 22 21  8 
13 12 11 10  9 

Scoring

By solving this problem you score 10 points.