#include<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int n,d;

bool inside(int x,int y){
	if(x>=0 && x<d && y>=0 && y<d)return true;
	else return false;
}

int main(){
	cin>>n;
	rep(p,n){
		if(p!=0)cout<<endl;
		cin>>d;
		char ch[d][d];
		rep(i,d)rep(j,d)ch[i][j]='.';
		int dir=0;
		int x=0,y=d-1;
		while(1){
			int check=0;
			if(dir==0){
				while(inside(x,y)){
					ch[y][x]='#';
					if(inside(x,y-1) && ch[y-1][x]=='.'){
						ch[y][x+1]='-';
						y--;
						check|=1;
					}else{if(ch[y][x+1]!='-')x++;break;} 
				}
			}else if(dir==1){
				while(inside(x,y)){
					ch[y][x]='#';
					if(inside(x+1,y) && ch[y][x+1]=='.'){
						ch[y+1][x]='-';
						x++;
						check|=2;
					}else{if(ch[y+1][x]!='-')y++;break;}
				}
			}else if(dir==2){
				while(inside(x,y)){
					ch[y][x]='#';
					if(inside(x,y+1) && ch[y+1][x]=='.'){
						ch[y][x-1]='-';
						y++;
						check|=4;
					}else{if(ch[y][x-1]!='-')x--;break;}
				}
			}else{
				while(inside(x,y)){
					ch[y][x]='#';
					if(inside(x-1,y) && ch[y][x-1]=='.'){
						ch[y-1][x]='-';
						x--;
						check|=8;
					}else{if(ch[y-1][x]!='-')y--;break;}
				}
			}
			dir++;
			dir%=4;
			if(check==0)break;
		}
		rep(i,d){
			rep(j,d){
				if(ch[i][j]=='#')cout<<'#';
				else cout<<' ';
			}
			cout<<endl;
		}
	}
	return 0;
}
### Prompt

Please create a solution in CPP 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<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int n,d;

bool inside(int x,int y){
	if(x>=0 && x<d && y>=0 && y<d)return true;
	else return false;
}

int main(){
	cin>>n;
	rep(p,n){
		if(p!=0)cout<<endl;
		cin>>d;
		char ch[d][d];
		rep(i,d)rep(j,d)ch[i][j]='.';
		int dir=0;
		int x=0,y=d-1;
		while(1){
			int check=0;
			if(dir==0){
				while(inside(x,y)){
					ch[y][x]='#';
					if(inside(x,y-1) && ch[y-1][x]=='.'){
						ch[y][x+1]='-';
						y--;
						check|=1;
					}else{if(ch[y][x+1]!='-')x++;break;} 
				}
			}else if(dir==1){
				while(inside(x,y)){
					ch[y][x]='#';
					if(inside(x+1,y) && ch[y][x+1]=='.'){
						ch[y+1][x]='-';
						x++;
						check|=2;
					}else{if(ch[y+1][x]!='-')y++;break;}
				}
			}else if(dir==2){
				while(inside(x,y)){
					ch[y][x]='#';
					if(inside(x,y+1) && ch[y+1][x]=='.'){
						ch[y][x-1]='-';
						y++;
						check|=4;
					}else{if(ch[y][x-1]!='-')x--;break;}
				}
			}else{
				while(inside(x,y)){
					ch[y][x]='#';
					if(inside(x-1,y) && ch[y][x-1]=='.'){
						ch[y-1][x]='-';
						x--;
						check|=8;
					}else{if(ch[y-1][x]!='-')y--;break;}
				}
			}
			dir++;
			dir%=4;
			if(check==0)break;
		}
		rep(i,d){
			rep(j,d){
				if(ch[i][j]=='#')cout<<'#';
				else cout<<' ';
			}
			cout<<endl;
		}
	}
	return 0;
}
```