#include<iostream>
using namespace std;

#define MAX 104

enum direction{UP,RIGHT,DOWN,LEFT};

int main()
{
	int d;
	cin >> d;

	for(int x = 0; x < d; ++x){
		int n;
		int s, t;
		int dir;
		short m[MAX][MAX] = {{0,}};
		cin >> n;

		if( x > 0 )
			cout << endl;

		for(int i = 0; i < n + 4; ++i){
			if( i == 0 || i == n+3 )
				for(int j = 1; j < n+3; ++j)
					m[i][j] = 1;
			m[i][0] = m[i][n+3] = 1;
		}

		s = n + 1;
		t = 2;
		dir = UP;
		while( true )
		{
			int cnt = 0;
			const int ds[] = {-1,0,1,0};
			const int dt[] = {0,1,0,-1};

			m[s][t] = 1;

			for(int i = 0; i < 4; ++i){
				if( m[ s + ds[i] ][ t + dt[i] ] )
					++cnt;
			}
			if( cnt >= 2 ){
				m[s][t] = 0;
				break;
			}

			switch( dir ){
				case UP: if( m[s-2][t] ) dir = RIGHT; break;
				case RIGHT: if( m[s][t+2] ) dir = DOWN; break;
				case DOWN: if( m[s+2][t] ) dir = LEFT; break;
				case LEFT: if( m[s][t-2] ) dir = UP; break;
			}
			switch( dir ){
				case UP: --s; break;
				case RIGHT: ++t; break;
				case DOWN: ++s; break;
				case LEFT: --t; break;
			}
		}

		for(int i = 2; i < n + 2; ++i){
			for(int j = 2; j < n + 2; ++j)
				cout << ( m[i][j] ? '#' : ' ' );
			cout << endl;
		}
	}
	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<iostream>
using namespace std;

#define MAX 104

enum direction{UP,RIGHT,DOWN,LEFT};

int main()
{
	int d;
	cin >> d;

	for(int x = 0; x < d; ++x){
		int n;
		int s, t;
		int dir;
		short m[MAX][MAX] = {{0,}};
		cin >> n;

		if( x > 0 )
			cout << endl;

		for(int i = 0; i < n + 4; ++i){
			if( i == 0 || i == n+3 )
				for(int j = 1; j < n+3; ++j)
					m[i][j] = 1;
			m[i][0] = m[i][n+3] = 1;
		}

		s = n + 1;
		t = 2;
		dir = UP;
		while( true )
		{
			int cnt = 0;
			const int ds[] = {-1,0,1,0};
			const int dt[] = {0,1,0,-1};

			m[s][t] = 1;

			for(int i = 0; i < 4; ++i){
				if( m[ s + ds[i] ][ t + dt[i] ] )
					++cnt;
			}
			if( cnt >= 2 ){
				m[s][t] = 0;
				break;
			}

			switch( dir ){
				case UP: if( m[s-2][t] ) dir = RIGHT; break;
				case RIGHT: if( m[s][t+2] ) dir = DOWN; break;
				case DOWN: if( m[s+2][t] ) dir = LEFT; break;
				case LEFT: if( m[s][t-2] ) dir = UP; break;
			}
			switch( dir ){
				case UP: --s; break;
				case RIGHT: ++t; break;
				case DOWN: ++s; break;
				case LEFT: --t; break;
			}
		}

		for(int i = 2; i < n + 2; ++i){
			for(int j = 2; j < n + 2; ++j)
				cout << ( m[i][j] ? '#' : ' ' );
			cout << endl;
		}
	}
	return 0;
}
```