Spiral Pattern

Time Limit : 1 sec, Memory Limit : 65536 KB

ぐるぐる模様

「ぐるぐる模様」を表示するプログラムを作成することにしました。「ぐるぐる模様」は以下のようなものとします。

  • 1 辺の長さが n の場合、nn 列の文字列として表示する。
  • 左下隅を基点とし,時計回りに回転する渦状の模様とする。
  • 線のある部分は #(半角シャープ)、空白部分は " "(半角空白)で表現する。
  • 線と線の間は空白を置く。

整数 n を入力とし,1 辺の長さが n の「ぐるぐる模様」を出力するプログラムを作成してください。

Input

入力は以下の形式で与えられます。

d
n1
n2
:
nd

1行目にデータセットの数 d (d ≤ 20)、続く d 行に i 個目のぐるぐる模様の辺の長さ ni (1 ≤ ni ≤ 100) がそれぞれ1行に与えられます。

Output

データセットごとに、ぐるぐる模様を出力してください。データセットの間に1行の空行を入れてください。

Sample Input

2
5
6

Output for the Sample Input

#####
#   #
# # #
# # #
# ###

######
#    #
# ## #
# #  #
# #  #
# ####

Source: PC Koshien 2006 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2006
http://www.pref.fukushima.jp/pc-concours/