#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

char field[101][101];

int dy[]={0,-1,0,1};
int dx[]={-1,0,1,0};
int n;

bool check(int x,int y,int angle){
	if(!(y>=0&&x>=0&&y<n&&x<n)){
		return false;
	}

	for(int i = 0; i < 4; i++){
		if(angle==i)
			continue;
		int nx=dx[i]+x;
		int ny=dy[i]+y;
		if(!(ny>=0&&nx>=0&&ny<n&&nx<n)){
			continue;
		}
		if(field[ny][nx]=='#'){
			return false;
		}
	}
	return true;
}

int main(){

	int nn;
	cin>>nn;
	for(int i = 0; i < nn; i++){
		if(i!=0)
			cout<<endl;
		cin>>n;
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				field[j][k]=' ';
			}
		}

		// 0:ツ右,1:ツ可コ,2:ツ債カ,3:ツ湘」
		int angle=3;
		int cx=0;
		int cy=n-1;
		int cnt=0;
		field[cy][cx]='#';
		while(1){
			if(angle==3){
				int ny=cy-1;
				int nx=cx;
				if(check(nx,ny,angle)){
					field[ny][nx]='#';
					cnt=0;
					cy=ny;
					cx=nx;
				}
				else{
					if(cnt>=1){
						break;
					}
					cnt++;
					angle=0;
				}
			}
			else if(angle==2){
				int ny=cy;
				int nx=cx-1;
				if(check(nx,ny,angle)){
					field[ny][nx]='#';
					cnt=0;
					cy=ny;
					cx=nx;
				}
				else{
					if(cnt>=1){
						break;
					}
					cnt++;
					angle=3;
				}
			}
			else if(angle==1){
				int ny=cy+1;
				int nx=cx;
				if(check(nx,ny,angle)){
					field[ny][nx]='#';
					cnt=0;
					cy=ny;
					cx=nx;
				}
				else{
					if(cnt>=1){
						break;
					}
					cnt++;
					angle=2;
				}
			}
			else if(angle==0){
				int ny=cy;
				int nx=cx+1;
				if(check(nx,ny,angle)){
					field[ny][nx]='#';
					cnt=0;
					cy=ny;
					cx=nx;
				}
				else{
					if(cnt>=1){
						break;
					}
					cnt++;
					angle=1;
				}
			}
		}
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				cout<<field[j][k];
			}
			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>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

char field[101][101];

int dy[]={0,-1,0,1};
int dx[]={-1,0,1,0};
int n;

bool check(int x,int y,int angle){
	if(!(y>=0&&x>=0&&y<n&&x<n)){
		return false;
	}

	for(int i = 0; i < 4; i++){
		if(angle==i)
			continue;
		int nx=dx[i]+x;
		int ny=dy[i]+y;
		if(!(ny>=0&&nx>=0&&ny<n&&nx<n)){
			continue;
		}
		if(field[ny][nx]=='#'){
			return false;
		}
	}
	return true;
}

int main(){

	int nn;
	cin>>nn;
	for(int i = 0; i < nn; i++){
		if(i!=0)
			cout<<endl;
		cin>>n;
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				field[j][k]=' ';
			}
		}

		// 0:ツ右,1:ツ可コ,2:ツ債カ,3:ツ湘」
		int angle=3;
		int cx=0;
		int cy=n-1;
		int cnt=0;
		field[cy][cx]='#';
		while(1){
			if(angle==3){
				int ny=cy-1;
				int nx=cx;
				if(check(nx,ny,angle)){
					field[ny][nx]='#';
					cnt=0;
					cy=ny;
					cx=nx;
				}
				else{
					if(cnt>=1){
						break;
					}
					cnt++;
					angle=0;
				}
			}
			else if(angle==2){
				int ny=cy;
				int nx=cx-1;
				if(check(nx,ny,angle)){
					field[ny][nx]='#';
					cnt=0;
					cy=ny;
					cx=nx;
				}
				else{
					if(cnt>=1){
						break;
					}
					cnt++;
					angle=3;
				}
			}
			else if(angle==1){
				int ny=cy+1;
				int nx=cx;
				if(check(nx,ny,angle)){
					field[ny][nx]='#';
					cnt=0;
					cy=ny;
					cx=nx;
				}
				else{
					if(cnt>=1){
						break;
					}
					cnt++;
					angle=2;
				}
			}
			else if(angle==0){
				int ny=cy;
				int nx=cx+1;
				if(check(nx,ny,angle)){
					field[ny][nx]='#';
					cnt=0;
					cy=ny;
					cx=nx;
				}
				else{
					if(cnt>=1){
						break;
					}
					cnt++;
					angle=1;
				}
			}
		}
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				cout<<field[j][k];
			}
			cout<<endl;
		}
	}

	return 0;
}
```