#include <iostream>
#include <cstdio>
#include <cstring>

char MAP[104][104];
int nx,ny,vx=0,vy=-1;
void rotate(){ //EñèÉñ]·é
	int tx=vx,ty=vy;
	vx=-ty;vy=tx;
}
int main(){
	int s; //}bvÌL³
	int n; //·éÂ
	int t; //I¹»èp
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&s);
		memset(MAP,'#',104*104);
		for(int x=1;x<1+s+2;x++){
			for(int y=1;y<1+s+2;y++){
				MAP[x][y]=' ';
			}
		}
		nx=2,ny=s+1;t=0;vx=0;vy=-1;
		while(1){
			MAP[nx][ny]='#';
			if(MAP[nx+vx*2][ny+vy*2]=='#'){
				if(t>0) break;
				t=2;
				rotate();
			} else {
				t--;
				nx+=vx;ny+=vy;
			}
		}
		//\¦
		if(i!=0) puts("");
		for(int y=2;y<1+s+1;y++){
			for(int x=2;x<1+s+1;x++){
				printf("%c",MAP[x][y]);
			}
			puts("");
		}
	}
	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>
#include <cstdio>
#include <cstring>

char MAP[104][104];
int nx,ny,vx=0,vy=-1;
void rotate(){ //EñèÉñ]·é
	int tx=vx,ty=vy;
	vx=-ty;vy=tx;
}
int main(){
	int s; //}bvÌL³
	int n; //·éÂ
	int t; //I¹»èp
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&s);
		memset(MAP,'#',104*104);
		for(int x=1;x<1+s+2;x++){
			for(int y=1;y<1+s+2;y++){
				MAP[x][y]=' ';
			}
		}
		nx=2,ny=s+1;t=0;vx=0;vy=-1;
		while(1){
			MAP[nx][ny]='#';
			if(MAP[nx+vx*2][ny+vy*2]=='#'){
				if(t>0) break;
				t=2;
				rotate();
			} else {
				t--;
				nx+=vx;ny+=vy;
			}
		}
		//\¦
		if(i!=0) puts("");
		for(int y=2;y<1+s+1;y++){
			for(int x=2;x<1+s+1;x++){
				printf("%c",MAP[x][y]);
			}
			puts("");
		}
	}
	return 0;
}
```