Problem F: Creating an odd magic square
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]
Description
A magic square is an n × n matrix in which n² numbers are arranged such that the sum of the numbers in each row, column, and two diagonals is the same. It is a type of magic circle. In a pure/normal magic square, each cell contains numbers from 1 to n². Magic squares always exist, except when n is 2.
Among these, the method for constructing odd-order magic squares is described by the French diplomat Simon de la Loubère in the section "The problem of the magical square according to the Indians" within his book *Du Royaume de Siam* (1693). The method is as follows:
Place 1 in the center cell of the first row. Next, repeat the process of placing natural numbers diagonally into the top-right cells until all cells are filled. If the corresponding cell extends beyond the top of the magic square, move it to the bottom cell; if it extends to the right, move it to the leftmost cell. Additionally, if the number extends beyond both the top and right of the magic square simultaneously, place it in the cell immediately below; if the cell to be filled is already occupied, place the number in the cell directly below it. (Refer to the figure below.)
Write a program that generates an n x n magic square when an arbitrary odd number n is input using this method.
Among these, the method for constructing odd-order magic squares is described by the French diplomat Simon de la Loubère in the section "The problem of the magical square according to the Indians" within his book *Du Royaume de Siam* (1693). The method is as follows:
Place 1 in the center cell of the first row. Next, repeat the process of placing natural numbers diagonally into the top-right cells until all cells are filled. If the corresponding cell extends beyond the top of the magic square, move it to the bottom cell; if it extends to the right, move it to the leftmost cell. Additionally, if the number extends beyond both the top and right of the magic square simultaneously, place it in the cell immediately below; if the cell to be filled is already occupied, place the number in the cell directly below it. (Refer to the figure below.)
Write a program that generates an n x n magic square when an arbitrary odd number n is input using this method.
Input
The number of test cases T is entered on the first line (1 <= T <= 20).
Starting from the next line, the size n of the magic square is entered as an odd number equal to the number of test cases (n is an odd number such that 1 <= n <= 31).
Starting from the next line, the size n of the magic square is entered as an odd number equal to the number of test cases (n is an odd number such that 1 <= n <= 31).
Output
For each test case, output the magic square created according to the method given in the problem description as an n x n matrix, with only a single space between the numbers and a single blank line between each result. (Refer to the output example.)
Sample Input Copy
2
3
5
Sample Output Copy
8 1 6
3 5 7
4 9 2
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9