마방진(魔方陣, 영어: magic square) 또는 방진(方陣)은 n²개의 수를 가로, 세로, 두 대각선 방향의 수를 더하면 모두 같은 값이 나오도록 n × n 행렬에 배열한 것이다. 마법진(魔法陣) 중 하나이다. 일반적인 마방진(pure/normal magic square)의 각 칸에는 1부터 n²까지의 수가 모두 들어간다. 마방진은 n이 2일 때를 제외하고 항상 존재한다.

이 중 홀수 차수의 마방진을 만드는 방법은 프랑스 외교관 '시몬 드 라 루베르'(Simon de la Loubère)가 그의 저서 《시암 왕국의 역사적 관계(Du Royaume de Siam, 1693)》의 〈인도인들에 따른 마방진 문제(The problem of the magical square according to the Indians)〉에 나와 있다. 그 방법은 다음과 같다.

첫 번째 행의 가운데 칸에 1을 넣는다. 그 다음 자연수를 대각선 방향으로 오른쪽 위 칸에 넣는 것을 모든 칸이 채워질 때까지 반복한다. 이때 해당하는 칸이 마방진의 위쪽으로 벗어난 경우에는 반대로 가장 아래쪽의 칸으로, 마방진의 오른쪽으로 벗어나는 경우는 가장 왼쪽의 칸으로 각자 한번 더 이동한다. 또한 마방진의 위쪽, 오른쪽을 동시에 벗어나는 경우에는 바로 아래 칸에 수를 넣도록 하며, 칸을 채울 자리에 이미 숫자가 있다면 바로 아래 칸에 수를 넣는다.(아래 그림 참조)




이러한 방법을 이용하여 임의의 홀수 n이 입력될 때 n x n 크기의 마방진을 생성하는 프로그램을 작성하시오.

첫 줄에 테스트케이스의 수 T가 입력된다.(1 <= T <= 20)
그 다음 줄부터 테스트케이스 수 만큼 마방진의 크기 n이 홀수로 입력된다.(n은 1 <= n <= 31 인 홀수)

각 테스트케이스에 대하여 문제 설명에서 주어진 방식으로 만들어진 마방진을 n x n의 행렬 형태로 출력하되 숫자들 사이에는 공백을 하나씩만 넣고 각 결과들 사이에는 빈 줄을 하나씩 넣는다.(출력 예시 참조)

2차원배열, ywwoo