#include <iostream>
#include <string>
#include <vector>

using namespace std;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

class Pos
{
public:
	int x, y;
};

void solve()
{
	int d;
	cin >> d;
	bool first = true;
	while(d--)
	{
		if(!first)
		{
			cout << endl;
		}
		first = false;
		int n;
		cin >> n;
		if(n == 1)
		{
			cout << "#" << endl;
			continue;
		}
		else if(n == 2)
		{
			cout << "##" << endl;
			cout << "# " << endl;
			continue;
		}
		vector< vector<char> > field(n, vector<char>(n, ' '));
		for(int i = 0; i < n; ++i)
		{
			field[i][0] = '#';
			field[i][n - 1] = '#';
			field[0][i] = '#';
		}
		int direction = 0;
		Pos current;
		current.x = n - 1;
		current.y = n - 1;
		while(true)
		{
			Pos next;
			next.x = current.x + dx[direction];
			next.y = current.y + dy[direction];
			int count = 0;
			while(field[next.y + dy[direction]][next.x + dx[direction]] != '#')
			{
				field[next.y][next.x] = '#';
				current = next;
				next.x = current.x + dx[direction];
				next.y = current.y + dy[direction];
				++count;
			}
			direction = (direction + 1) % 4;
			if(count < 2)
			{
				break;
			}
		}
		for(int i = 0; i < n; ++i)
		{
			for(int j = 0; j < n; ++j)
			{
				cout << field[i][j];
			}
			cout << endl;
		}
	}
}

int main()
{
	solve();
	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
#include <iostream>
#include <string>
#include <vector>

using namespace std;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

class Pos
{
public:
	int x, y;
};

void solve()
{
	int d;
	cin >> d;
	bool first = true;
	while(d--)
	{
		if(!first)
		{
			cout << endl;
		}
		first = false;
		int n;
		cin >> n;
		if(n == 1)
		{
			cout << "#" << endl;
			continue;
		}
		else if(n == 2)
		{
			cout << "##" << endl;
			cout << "# " << endl;
			continue;
		}
		vector< vector<char> > field(n, vector<char>(n, ' '));
		for(int i = 0; i < n; ++i)
		{
			field[i][0] = '#';
			field[i][n - 1] = '#';
			field[0][i] = '#';
		}
		int direction = 0;
		Pos current;
		current.x = n - 1;
		current.y = n - 1;
		while(true)
		{
			Pos next;
			next.x = current.x + dx[direction];
			next.y = current.y + dy[direction];
			int count = 0;
			while(field[next.y + dy[direction]][next.x + dx[direction]] != '#')
			{
				field[next.y][next.x] = '#';
				current = next;
				next.x = current.x + dx[direction];
				next.y = current.y + dy[direction];
				++count;
			}
			direction = (direction + 1) % 4;
			if(count < 2)
			{
				break;
			}
		}
		for(int i = 0; i < n; ++i)
		{
			for(int j = 0; j < n; ++j)
			{
				cout << field[i][j];
			}
			cout << endl;
		}
	}
}

int main()
{
	solve();
	return(0);
}
```