Lusrica 在一个 $n \times n$ 的网格板上设计了一个蚊香。蚊香由一系列连续的网格组成，其中每两个相邻的网格都共享一条公共边。如果蚊香中的两个网格不是连续的，它们就不会共享任何边，但它们可以共享一个公共端点。

Lusrica 设计的蚊香从棋盘的左上角开始。它向右延伸直到最后一个可用的网格。改变方向向下延伸直到最后一个可用的网格，再次改变方向向左延伸直到最后一个可用的网格。继续改变方向向上延伸直到最后一个可用的网格。然后再次向右延伸，并重复上述转向过程。

它最终会在一个无法继续进行上述过程的网格处结束。你的任务是打印出 Lusrica 蚊香的完整蓝图。

输入格式

本题包含多个测试用例，第一行包含一个整数 $t$ ($1 \le t \le 36$)，表示测试用例的数量。对于每个测试用例，输入一行包含一个整数 $n$ ($1 \le n \le 36$)，表示棋盘的大小。

输出格式

对于每个输入 $n$ 的测试用例，输出 $n$ 行来描述整个棋盘。每行包含 $n$ 个字符。如果某个网格是 Lusrica 蚊香的一部分，则对应字符为 '#'，否则为 ' '（单个空格）。

样例

输入格式 1

5
1
2
3
4
5

输出格式 1

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