#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int check(int,int,int);
int a[100][100];
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
int n;
int main(void)
{
	int i,j,k,deg,dd,cnt,x,y,xx,yy,d;
	int flg;
	scanf("%d",&d);
	for(k=0;k<d;k++)	{
		if(k!=0)	printf("\n");
		scanf("%d",&n);
		for(i=0;i<n;i++)	{
			for(j=0;j<n;j++)	{
				a[i][j]=0;
			}
		}
		y=n-1;	x=0;	deg=0;
		a[y][x]=1;
		flg=1;
		while(flg==1)	{
			if(check(x,y,deg)==0)	{
				dd=(deg+1)%4;
				if(check(x,y,dd)==0)	{
					flg=0;
					break;
				}
				else {
					deg=dd;
					x=x+dx[deg];	y=y+dy[deg];
					a[y][x]=1;
				}
			}
			else {
				x=x+dx[deg];	y=y+dy[deg];
				a[y][x]=1;		
			}
		}
		for(i=0;i<n;i++)	{
			for(j=0;j<n;j++)	{
				if(a[i][j]==1)	{
					printf("#");
				}
				else {
					printf(" ");
				}
			}
			printf("\n");
		}
	}
	return 0;
}
int check(int x,int y,int d1)
{
	int xx,yy,flg,i,j,dd,x2,y2;
	xx=x+dx[d1];	yy=y+dy[d1];
	if(xx<0 || xx>=n || yy<0 || yy>=n)	{
		return 0;
	}
	x2=xx+dx[d1];	y2=yy+dy[d1];
	if(x2>=0 && x2<n && y2>=0 && y2<n && a[y2][x2]==1)	{
		return 0;
	}
	dd=(d1+1)%4;
	x2=xx+dx[dd];	y2=yy+dy[dd];
	if(x2>=0 && x2<n && y2>=0 && y2<n && a[y2][x2]==1)	{
		return 0;
	}	
	return 1;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

I decided to create a program that displays a "round and round pattern". The "round and round pattern" is as follows.

* If the length of one side is n, it is displayed as a character string with n rows and n columns.
* A spiral pattern that rotates clockwise with the lower left corner as the base point.
* The part with a line is represented by # (half-width sharp), and the blank part is represented by "" (half-width blank).
* Leave a space between the lines.



Create a program that takes an integer n as an input and outputs a "round and round pattern" with a side length of n.



Input

The input is given in the following format:


d
n1
n2
::
nd


The number of datasets d (d ≤ 20) is given to the first line, and the side length ni (1 ≤ ni ≤ 100) of the i-th round pattern is given to each of the following d lines.

Output

Please output a round and round pattern for each data set. Insert a blank line between the datasets.

Example

Input

2
5
6


Output

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

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

### Response

```cpp
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int check(int,int,int);
int a[100][100];
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
int n;
int main(void)
{
	int i,j,k,deg,dd,cnt,x,y,xx,yy,d;
	int flg;
	scanf("%d",&d);
	for(k=0;k<d;k++)	{
		if(k!=0)	printf("\n");
		scanf("%d",&n);
		for(i=0;i<n;i++)	{
			for(j=0;j<n;j++)	{
				a[i][j]=0;
			}
		}
		y=n-1;	x=0;	deg=0;
		a[y][x]=1;
		flg=1;
		while(flg==1)	{
			if(check(x,y,deg)==0)	{
				dd=(deg+1)%4;
				if(check(x,y,dd)==0)	{
					flg=0;
					break;
				}
				else {
					deg=dd;
					x=x+dx[deg];	y=y+dy[deg];
					a[y][x]=1;
				}
			}
			else {
				x=x+dx[deg];	y=y+dy[deg];
				a[y][x]=1;		
			}
		}
		for(i=0;i<n;i++)	{
			for(j=0;j<n;j++)	{
				if(a[i][j]==1)	{
					printf("#");
				}
				else {
					printf(" ");
				}
			}
			printf("\n");
		}
	}
	return 0;
}
int check(int x,int y,int d1)
{
	int xx,yy,flg,i,j,dd,x2,y2;
	xx=x+dx[d1];	yy=y+dy[d1];
	if(xx<0 || xx>=n || yy<0 || yy>=n)	{
		return 0;
	}
	x2=xx+dx[d1];	y2=yy+dy[d1];
	if(x2>=0 && x2<n && y2>=0 && y2<n && a[y2][x2]==1)	{
		return 0;
	}
	dd=(d1+1)%4;
	x2=xx+dx[dd];	y2=yy+dy[dd];
	if(x2>=0 && x2<n && y2>=0 && y2<n && a[y2][x2]==1)	{
		return 0;
	}	
	return 1;
}

```