#include<stdio.h>
char out[100][101];
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
int main(){
	int a;
	scanf("%d",&a);
	while(a--){
		int b;
		scanf("%d",&b);
		for(int i=0;i<b;i++){
			for(int j=0;j<b;j++){
				out[i][j]=' ';
			}
			out[i][b]=0;
		}
		if(b==1){
			printf("#\n");
			if(a)printf("\n");
			continue;
		}
		if(b==2){
			printf("##\n# \n");
			if(a)printf("\n");
			continue;
		}
		int row=b-1;
		int col=0;
		int dir=0;
		int len=1;
		out[row][col]='#';
		while(1){
			int nrow=row+dy[dir%4];
			int ncol=col+dx[dir%4];
			if((dir%4==0&&nrow==0)||(dir%4==3&&ncol==0)||(dir%4==2&&nrow==b-1)||(dir%4==1&&ncol==b-1)){
				row=nrow;
				col=ncol;
				out[row][col]='#';
				dir++;
				len=1;
			}else if(out[nrow+dy[dir%4]][ncol+dx[dir%4]]=='#'){
				if(len<3)break;
				dir++;
				len=1;
			}else{
				row=nrow;
				col=ncol;
				out[row][col]='#';
				len++;
			}
		}
		for(int i=0;i<b;i++)printf("%s\n",out[i]);
		if(a)printf("\n");
	}
}
### Prompt

Construct a cpp code solution to the problem outlined:

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<stdio.h>
char out[100][101];
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
int main(){
	int a;
	scanf("%d",&a);
	while(a--){
		int b;
		scanf("%d",&b);
		for(int i=0;i<b;i++){
			for(int j=0;j<b;j++){
				out[i][j]=' ';
			}
			out[i][b]=0;
		}
		if(b==1){
			printf("#\n");
			if(a)printf("\n");
			continue;
		}
		if(b==2){
			printf("##\n# \n");
			if(a)printf("\n");
			continue;
		}
		int row=b-1;
		int col=0;
		int dir=0;
		int len=1;
		out[row][col]='#';
		while(1){
			int nrow=row+dy[dir%4];
			int ncol=col+dx[dir%4];
			if((dir%4==0&&nrow==0)||(dir%4==3&&ncol==0)||(dir%4==2&&nrow==b-1)||(dir%4==1&&ncol==b-1)){
				row=nrow;
				col=ncol;
				out[row][col]='#';
				dir++;
				len=1;
			}else if(out[nrow+dy[dir%4]][ncol+dx[dir%4]]=='#'){
				if(len<3)break;
				dir++;
				len=1;
			}else{
				row=nrow;
				col=ncol;
				out[row][col]='#';
				len++;
			}
		}
		for(int i=0;i<b;i++)printf("%s\n",out[i]);
		if(a)printf("\n");
	}
}
```