#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

bool guru[110][110];

int main() {
	int d=in();
	int n;
	bool first=true;
	while(d--){
		if(!first)cout<<endl;
		first=false;
		cin>>n;
		int i,j;
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				guru[i][j]=false;
			}
		}
		int len=n;
		for(i=0;i<n;i++){
			guru[i][0]=true;
		}
		while(1){
			for(i=0;i<len;i++){
				guru[(n-len)/2][i+(n-len)/2]=true;
			}
			if(len<3)break;
			for(i=0;i<len;i++){
				guru[i+(n-len)/2][n-1-(n-len)/2]=true;
			}
			len-=2;
			for(i=0;i<len;i++){
				guru[n-1-(n-len-2)/2][n-(n-len)/2-i]=true;
			}
			if(len<3)break;
			for(i=0;i<len;i++){
				guru[n-(n-len)/2-i][(n-len-2)/2+2]=true;
			}
			len-=2;
		}
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(guru[i][j])cout<<"#";
				else cout<<" ";
			}
			cout<<endl;
		}
	}
	return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

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<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

bool guru[110][110];

int main() {
	int d=in();
	int n;
	bool first=true;
	while(d--){
		if(!first)cout<<endl;
		first=false;
		cin>>n;
		int i,j;
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				guru[i][j]=false;
			}
		}
		int len=n;
		for(i=0;i<n;i++){
			guru[i][0]=true;
		}
		while(1){
			for(i=0;i<len;i++){
				guru[(n-len)/2][i+(n-len)/2]=true;
			}
			if(len<3)break;
			for(i=0;i<len;i++){
				guru[i+(n-len)/2][n-1-(n-len)/2]=true;
			}
			len-=2;
			for(i=0;i<len;i++){
				guru[n-1-(n-len-2)/2][n-(n-len)/2-i]=true;
			}
			if(len<3)break;
			for(i=0;i<len;i++){
				guru[n-(n-len)/2-i][(n-len-2)/2+2]=true;
			}
			len-=2;
		}
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(guru[i][j])cout<<"#";
				else cout<<" ";
			}
			cout<<endl;
		}
	}
	return 0;
}
```