// AOJ 0141
#include<iostream>
#include<cstring>

char ptn[104][105];
const int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int dir;

bool check( int x, int y, int dir )
{
	int nx = x + dx[dir], ny = y + dy[dir];

	for( int i = 0; i != 4; ++i )
	{
		int nnx = nx + dx[i], nny = ny + dy[i];

		if( nnx == x && nny == y )
			continue;

		if( ptn[nny][nnx] == '#' )
			return false;
	}

	return true;
}

int main()
{
	int d;
	std::cin >> d;
	while( d-- )
	{
		int n;
		std::cin >> n;

		for( int i = 0; i != n + 4; ++i )
			for( int j = 0; j != n + 4; ++j )
				ptn[i][j] = !i || !j || i == n + 3 || j == n + 3 ? '#' : ' ';

		int x = 2, y = n + 1;
		bool fl = false;
		dir = 0;

		while( true )
		{
			ptn[y][x] = '#';

			if( !check( x, y, dir ) )
			{
				if( !fl )
				{
					dir = ( dir + 1 ) & 3;
					fl = true;
					continue;
				}
				else
					break;
			}
			else
				fl = false;

			x += dx[dir];
			y += dy[dir];
		}

		for( int i = 2; i != n + 2; ++i )
		{
			for( int j = 2; j != n + 2; ++j )
				std::cout << ptn[i][j];

			std::cout << std::endl;
		}

		if( d )
			std::cout << std::endl;
	}

	return 0;
}
### Prompt

Please provide a cpp coded solution 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
// AOJ 0141
#include<iostream>
#include<cstring>

char ptn[104][105];
const int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int dir;

bool check( int x, int y, int dir )
{
	int nx = x + dx[dir], ny = y + dy[dir];

	for( int i = 0; i != 4; ++i )
	{
		int nnx = nx + dx[i], nny = ny + dy[i];

		if( nnx == x && nny == y )
			continue;

		if( ptn[nny][nnx] == '#' )
			return false;
	}

	return true;
}

int main()
{
	int d;
	std::cin >> d;
	while( d-- )
	{
		int n;
		std::cin >> n;

		for( int i = 0; i != n + 4; ++i )
			for( int j = 0; j != n + 4; ++j )
				ptn[i][j] = !i || !j || i == n + 3 || j == n + 3 ? '#' : ' ';

		int x = 2, y = n + 1;
		bool fl = false;
		dir = 0;

		while( true )
		{
			ptn[y][x] = '#';

			if( !check( x, y, dir ) )
			{
				if( !fl )
				{
					dir = ( dir + 1 ) & 3;
					fl = true;
					continue;
				}
				else
					break;
			}
			else
				fl = false;

			x += dx[dir];
			y += dy[dir];
		}

		for( int i = 2; i != n + 2; ++i )
		{
			for( int j = 2; j != n + 2; ++j )
				std::cout << ptn[i][j];

			std::cout << std::endl;
		}

		if( d )
			std::cout << std::endl;
	}

	return 0;
}
```