#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

void solve(int n)
{
	if(n==1){
		cout<<"#"<<endl;
		return;
	}
	vs a(n,string(n,'#'));
	int di[]={-1,0,1,0};
	int dj[]={0,1,0,-1};
	int ci=n-1,cj=1,k=0;
	rep(i,10000){
		a[ci][cj]=' ';
		int ti=ci+di[k]*2,tj=cj+dj[k]*2;
		if(ti<0 || n<=ti || tj<0 || n<=tj || a[ti][tj]==' ')
			k=(k+1)%4;
		else{
			ci+=di[k];
			cj+=dj[k];
		}
	}
	rep(i,n)
		cout<<a[i]<<endl;
}

int main()
{
	int d; cin>>d;
	rep(i,d){
		if(i) cout<<endl;
		int n; cin>>n;
		solve(n);
	}
	
	return 0;
}
### Prompt

Your challenge is to write a CPP solution 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 <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

void solve(int n)
{
	if(n==1){
		cout<<"#"<<endl;
		return;
	}
	vs a(n,string(n,'#'));
	int di[]={-1,0,1,0};
	int dj[]={0,1,0,-1};
	int ci=n-1,cj=1,k=0;
	rep(i,10000){
		a[ci][cj]=' ';
		int ti=ci+di[k]*2,tj=cj+dj[k]*2;
		if(ti<0 || n<=ti || tj<0 || n<=tj || a[ti][tj]==' ')
			k=(k+1)%4;
		else{
			ci+=di[k];
			cj+=dj[k];
		}
	}
	rep(i,n)
		cout<<a[i]<<endl;
}

int main()
{
	int d; cin>>d;
	rep(i,d){
		if(i) cout<<endl;
		int n; cin>>n;
		solve(n);
	}
	
	return 0;
}
```