#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdio>
#include <cmath>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main()
{
	int d;
	scanf("%d", &d);
	rep(i, d){
		int n;
		scanf("%d", &n);
		
		char field[128][128];
		rep(j, n){
			fill(field[j], field[j]+n, ' ');
			field[j][n] = '\0';
		}
		
		const int dy[] = {-1, 0, 1, 0};
		const int dx[] = {0, 1, 0, -1};
		int y=n-1, x=0;
		field[y][x] = '#';
		int dir = 0;
		int okok = 0;
		for(;;){
			int py = y + dy[dir];
			int px = x + dx[dir];
			
			bool ok = true;
			if(py<0 || n<=py || px<0 || n<=px)
				ok = false;
			
			rep(j, 4){
				int ny = py + dy[j];
				int nx = px + dx[j];
				if(ny<0 || n<=ny || nx<0 || n<=nx || (y==ny && x==nx))
					continue;
				
				if(field[ny][nx] == '#'){
					ok = false;
					j=3;
					break;
				}
			}
			
			if(!ok){
				dir = (dir+1) % 4;
				++okok;
				if(okok == 4)
					break;
				continue;
			}
			else
				okok = 0;
			
			y = py;
			x = px;
			field[y][x] = '#';
		}
		
		if(i) puts("");
		rep(j, n)
			puts(field[j]);
	}
	return 0;
}
### Prompt

In Cpp, your task is to solve 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 <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdio>
#include <cmath>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main()
{
	int d;
	scanf("%d", &d);
	rep(i, d){
		int n;
		scanf("%d", &n);
		
		char field[128][128];
		rep(j, n){
			fill(field[j], field[j]+n, ' ');
			field[j][n] = '\0';
		}
		
		const int dy[] = {-1, 0, 1, 0};
		const int dx[] = {0, 1, 0, -1};
		int y=n-1, x=0;
		field[y][x] = '#';
		int dir = 0;
		int okok = 0;
		for(;;){
			int py = y + dy[dir];
			int px = x + dx[dir];
			
			bool ok = true;
			if(py<0 || n<=py || px<0 || n<=px)
				ok = false;
			
			rep(j, 4){
				int ny = py + dy[j];
				int nx = px + dx[j];
				if(ny<0 || n<=ny || nx<0 || n<=nx || (y==ny && x==nx))
					continue;
				
				if(field[ny][nx] == '#'){
					ok = false;
					j=3;
					break;
				}
			}
			
			if(!ok){
				dir = (dir+1) % 4;
				++okok;
				if(okok == 4)
					break;
				continue;
			}
			else
				okok = 0;
			
			y = py;
			x = px;
			field[y][x] = '#';
		}
		
		if(i) puts("");
		rep(j, n)
			puts(field[j]);
	}
	return 0;
}
```