Your task is to draw a square of size n*n but you have to distinguish the inner area from the circumference.

The edge should be drawn using the character '#'.

The inner area should be drawn using the character '='.

Here is the first few squares:

size 1:

#

size 2:

##
##

Input

The first line contains one integer T the number of test cases (T < 50), then T lines follows each with integer n the size of the required square (n < 50).

Output

for each test case draw the required square, please separate every case by an empty line.

Example

Input:
2
3
4

Output:
###
#=#
###

####
#==#
#==#
####