COETEST5

Cho số N là kích thước của ma trận vuông NxN. Ban đầu ma trận chưa được điền số.
Hãy viết chương trình điền các số từ 1 đến N*N vào ma trận biết số 1 luôn nằm ở vị trí chính giữa của hàng đầu tiên .
Các số từ 2 đến N*N sẽ được điền theo quy tắc sau:
Ô màu vàng thể hiện vị trí hiện tại, ô màu đỏ thể hiện ví trí tiếp theo cần xét
Quy tắc 1. Xét vị trí ở hàng phía dưới và chếch sang trái 1 ô so với vị trí hiện tại (như hình dưới), nếu vị trí này trống thì điền số tiếp theo vào đây.

- Trong trường hợp vị trí hiện tại đang ở hàng dưới cùng thì xét vị trí tiếp theo ở hàng trên cùng (như hình dưới).

- Trong trường hợp vị trí hiện tại đang ở cột ngoài cùng bên trái thì xét vị trí tiếp theo ở cột ngoài cùng bên phải (như hình dưới).

- Trong trường hợp vị trí hiện tại đang ở cột ngoài cùng bên trái và hàng cuối cùng thì xét vị trí tiếp theo ở cột ngoài cùng bên phải và hàng đầu tiên (như hình dưới).

 
Quy tắc 2. Nếu vị trí xét theo quy tắc số 1 đã được điền số trước đó thì xét vị trí ở ngay hàng phía trên so với vị trí hiện tại (như hình dưới).

- Trong trường hợp vị trí hiện tại đang ở hàng trên cùng thì xét vị trí tiếp theo là ở hàng dưới cùng (như hình dưới)

Quy tắc 3. Tiếp tục thực hiện lần lượt theo quy tắc số 1 và quy tắc số 2 cho đến khi hoàn thành ma trận (lưu ý: luôn ưu tiên xét quy tắc số 1 trước, khi quy tắc số 1 không thể điền được thì xét quy tắc số 2).
Ví dụ:
Cho N = 3, chúng ta cần điền các số từ 1 đến 9 vào ma trận 3x3.
Các bước thực hiện lần lượt như sau:
1. Số 1 luôn nằm ở vị trí chính giữa của hàng đầu tiên, vậy ta có vị trí hiện tại là vị trí (0, 1):


2. Vị trí hiện tại đang là (0, 1), áp dụng quy tắc số 1 ta có vị trí cần xét tiếp theo là (1, 0). Vì vị trí (1, 0) chưa được điền số vì vậy ta có thể điền số tiếp theo tại đây.


3. Vị trí hiện tại đang là (1, 0), áp dụng quy tắc số 1 ta có vị trí cần xét tiếp theo là (2, 2). Vì vị trí (2, 2) chưa được điền số vì vậy ta có thể điền số tiếp theo tại đây.


4. Vị trí hiện tại đang là (2, 2), áp dụng quy tắc số 1 ta có vị trí cần xét tiếp theo là (0, 1). Vì vị trí (0, 1) đã được điền số trước đó cho nên ta phải áp dụng quy tắc số 2.
Vị trí hiện tại đang là (2, 2), áp dụng quy tắc số 2 ta có vị trí cần điền số là (1, 2).


5. Vị trí hiện tại đang là (1, 2), áp dụng quy tắc số 1 ta có vị trí cần xét tiếp theo là (2, 1). Vì vị trí (2, 1) chưa được điền số vì vậy ta có thể điền số tiếp theo tại đây.


6. Vị trí hiện tại đang là (2, 1), áp dụng quy tắc số 1 ta có vị trí cần xét tiếp theo là (0, 0). Vì vị trí (0, 0) chưa được điền số vì vậy ta có thể điền số tiếp theo tại đây.

7. Vị trí hiện tại đang là (0, 0), áp dụng quy tắc số 1 ta có vị trí cần xét tiếp theo là (1, 2). Vì vị trí (1, 2) đã được điền số trước đó cho nên ta phải áp dụng quy tắc số 2.
Vị trí hiện tại đang là (0, 0), áp dụng quy tắc số 2 ta có vị trí cần điền số là (2, 0).

8. Vị trí hiện tại đang là (2, 0), áp dụng quy tắc số 1 ta có vị trí cần xét tiếp theo là (0, 2). Vì vị trí (0, 2) chưa được điền số vì vậy ta có thể điền số tiếp theo tại đây.

9. Vị trí hiện tại đang là (0, 2), áp dụng quy tắc số 1 ta có vị trí cần xét tiếp theo là (1, 1). Vì vị trí (1, 1) chưa được điền số vì vậy ta có thể điền số tiếp theo tại đây.

Input

Dòng đầu tiên của input là số lượng test case T (T <= 50).
Mỗi test case gồm 1 dòng duy nhất chứa kích thước ma trận N (N <= 100).
Đảm bảo N luôn là số lẻ.

Output

In kết quả theo định dạng sau: ký tự đầu tiên là “#”, tiếp theo là số thứ tự của test case, tiếp theo là xuống dòng và cuối cùng là ma trận đã được điền số.
Mỗi hàng của ma trận phân biệt nhau bởi xuống dòng.
Trong một hàng của ma trận, các số phân biệt nhau bởi dấu cách.

Example

Input:
2
3
5

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