Ma Trận Không Kề Nhau

Hai số nguyên được gọi là liên tiếp nếu hiệu tuyệt đối của chúng bằng $1$. Hai ô trong một ma trận được gọi là kề nhau nếu chúng có chung một cạnh.

Với mỗi số nguyên $n$, hãy điền các số từ $1$ đến $n^2$ vào một ma trận vuông $n\times n$, mỗi số xuất hiện đúng một lần, sao cho hai ô kề nhau không bao giờ chứa hai số liên tiếp. Nếu có nhiều ma trận hợp lệ, bạn có thể in bất kỳ ma trận nào.

Input

• Dòng đầu chứa số nguyên $t$ - số bộ test.
• Mỗi bộ test gồm một dòng chứa số nguyên $n$.

Output

• Với mỗi bộ test, in $-1$ trên một dòng nếu không tồn tại ma trận hợp lệ.
• Ngược lại, in $n$ dòng, mỗi dòng gồm $n$ số nguyên mô tả một ma trận thỏa mọi điều kiện. Các bộ test được in liên tiếp; không bắt buộc có dòng trống ngăn cách.

Constraints

• $1\le t\le 100$.
• $1\le n\le 100$.
• Mỗi số từ $1$ đến $n^2$ phải xuất hiện đúng một lần trong đáp án khác $-1$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 3$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4
1
2
3
4

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