#include <iostream>
#include <cstring>
#define rep(i,n) for(int i=0;i<(n);i++)
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LIFT 3

using namespace std;

bool p[100][100];

void dfs (int len, int dir, int r, int c, int cnt )
{
	if (len <= 1 )
		return;

	dir = (dir + 1) % 4;
	if (cnt != 0 && cnt % 2 == 0 ){
		len -= 2;
	} // end if 

	int cr = r, cc = c;
	switch (dir ){
		case UP:
			for (int i = 0; i < len; i++, cr-- )
				p[cr][cc] = true;
			cr++;
			break;
		case DOWN:
			for (int i = 0; i < len; i++, cr++ )
				p[cr][cc] = true;
			cr--;
			break;	
		case RIGHT:
			for (int j = 0; j < len; j++, cc++ )
				p[cr][cc] = true;
			cc--;
			break;
		case LIFT:
			for (int j = 0; j < len; j++, cc-- )
				p[cr][cc] = true;
			cc++;
			break;
	} // end switch

	if (len == 2 )
		return;

	dfs (len, dir, cr, cc, cnt + 1 );
}

void disp_p (int m )
{
	rep (i, m ){
		rep (j, m ){
			if (p[i][j] )
				cout << '#';
			else
				cout << ' ';
		}// end rep
		cout << endl;
	} // end rep
}

int main()
{
	int n;

	while (cin >> n && n ){
		for (int i = 0; i < n; i++ ){
			int m;
			cin >> m;
			if (m == 1 ){
				cout << "#" << endl;
			}else if (m == 2 ){
				cout << "##" << endl;
				cout << "# " << endl;
			}else{
				memset (p, false, sizeof (p ) );
				for (int r = m - 1; r >= 0; r-- )
					p[r][0] = true;
				for (int c = 0; c < m; c++ )
					p[0][c] = true;
				for (int r = 0; r < m; r++ )
					p[r][m-1] = true;
				dfs (m-2, DOWN, m-1, m-1, 0 );
				disp_p (m );
			} // end if
			if (i != n - 1 ){
				cout << endl;
			} // end if
		} // end if
	} // end whlie

	return 0;
}
### Prompt

Generate 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 <cstring>
#define rep(i,n) for(int i=0;i<(n);i++)
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LIFT 3

using namespace std;

bool p[100][100];

void dfs (int len, int dir, int r, int c, int cnt )
{
	if (len <= 1 )
		return;

	dir = (dir + 1) % 4;
	if (cnt != 0 && cnt % 2 == 0 ){
		len -= 2;
	} // end if 

	int cr = r, cc = c;
	switch (dir ){
		case UP:
			for (int i = 0; i < len; i++, cr-- )
				p[cr][cc] = true;
			cr++;
			break;
		case DOWN:
			for (int i = 0; i < len; i++, cr++ )
				p[cr][cc] = true;
			cr--;
			break;	
		case RIGHT:
			for (int j = 0; j < len; j++, cc++ )
				p[cr][cc] = true;
			cc--;
			break;
		case LIFT:
			for (int j = 0; j < len; j++, cc-- )
				p[cr][cc] = true;
			cc++;
			break;
	} // end switch

	if (len == 2 )
		return;

	dfs (len, dir, cr, cc, cnt + 1 );
}

void disp_p (int m )
{
	rep (i, m ){
		rep (j, m ){
			if (p[i][j] )
				cout << '#';
			else
				cout << ' ';
		}// end rep
		cout << endl;
	} // end rep
}

int main()
{
	int n;

	while (cin >> n && n ){
		for (int i = 0; i < n; i++ ){
			int m;
			cin >> m;
			if (m == 1 ){
				cout << "#" << endl;
			}else if (m == 2 ){
				cout << "##" << endl;
				cout << "# " << endl;
			}else{
				memset (p, false, sizeof (p ) );
				for (int r = m - 1; r >= 0; r-- )
					p[r][0] = true;
				for (int c = 0; c < m; c++ )
					p[0][c] = true;
				for (int r = 0; r < m; r++ )
					p[r][m-1] = true;
				dfs (m-2, DOWN, m-1, m-1, 0 );
				disp_p (m );
			} // end if
			if (i != n - 1 ){
				cout << endl;
			} // end if
		} // end if
	} // end whlie

	return 0;
}
```