Magic Square

Time Limit : 1 sec, Memory Limit : 65536 KB

魔方陣

n × n の正方形のマス目の中に数字の1から n × n が一つずつ入っていて、縦のどの列のマス目の和も、横のどの列のマス目の和も対角線のマス目の和も等しいものを魔方陣といいます。

一辺のマスの個数が奇数の魔方陣の作り方には以下の方法があります。

  1. 中央のマス目のちょうど一つ下のマス目に1を入れる。
  2. 次の数字を右斜め下のマス目に入れる。
    ただし、数字を入れようとしたマス目が正方形からはみ出している場合、すでに数字が埋まっている場合は以下の方法に従って数字を入れるマス目を探す。
    • 右にはみ出した場合には、同じ行の左はしに、左にはみ出した場合には、同じ行の右はしに、下にはみ出した場合には、同じ列の一番上に数字を入れる。
    • 数字を入れようとしたマス目が埋まっているときには、その埋まっているマス目の左斜め下のマス目に入れる。
  3. 全てのマス目が埋まるまで2を繰り返す。

この方法に従って、一辺のマス目の個数 n を入力として、その大きさの魔方陣を出力するプログラムを作成して下さい。ただし、n は 3 以上 15 以下の奇数とします。マス目に入る各数字は右詰 4 桁で出力してください。

入力

複数の入力が与えられます。各入力で n (正の整数)が1行に与えられます。入力は 0 で終了します。入力の数は 10 を超えません。

出力

各入力に対して n × n の魔方陣を出力して下さい。

Sample Input

3
5
0

Output for the Sample Input

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

Source: PC Koshien 2005 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2005
(extended format)
http://www.pref.fukushima.jp/pc-concours/