#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>


typedef long long ll;
const double Eps = 1e-6;

using namespace std;

int main()
{
	int d;
	scanf("%d", &d);
	while (d--)
	{
		int n;
		scanf("%d", &n);
		bool maze[126][126];
		memset(maze, 0, sizeof(maze));
		for (int i = 0; i < n+4; ++i)
			maze[0][i] = maze[i][0] = maze[n+3][i] = maze[i][n+3] = true;

		int x = 2;
		int y = n+1;
		int dx[] = { 0, 1, 0, -1 };
		int dy[] = { -1, 0, 1, 0 };
		int dir = 0;
		while (true)
		{
			int c = 0;
			for (int i = 0; i < 4; ++i)
				if (maze[y+dy[i]][x+dx[i]])
					++c;
			if (c > 1)
				break;

			maze[y][x] = true;
			int tx = x + 2*dx[dir];
			int ty = y + 2*dy[dir];
			if (maze[ty][tx])
				dir = (dir+1) % 4;

			x += dx[dir];
			y += dy[dir];
		}
		for (int i = 2; i < n+2; ++i)
		{
			for (int j = 2; j < n+2; ++j)
				putchar(maze[i][j] ? '#' : ' ');
			putchar('\n');
		}
		if (d)
			putchar('\n');
	}

	return 0;
}
### Prompt

Your task is to create 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 <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>


typedef long long ll;
const double Eps = 1e-6;

using namespace std;

int main()
{
	int d;
	scanf("%d", &d);
	while (d--)
	{
		int n;
		scanf("%d", &n);
		bool maze[126][126];
		memset(maze, 0, sizeof(maze));
		for (int i = 0; i < n+4; ++i)
			maze[0][i] = maze[i][0] = maze[n+3][i] = maze[i][n+3] = true;

		int x = 2;
		int y = n+1;
		int dx[] = { 0, 1, 0, -1 };
		int dy[] = { -1, 0, 1, 0 };
		int dir = 0;
		while (true)
		{
			int c = 0;
			for (int i = 0; i < 4; ++i)
				if (maze[y+dy[i]][x+dx[i]])
					++c;
			if (c > 1)
				break;

			maze[y][x] = true;
			int tx = x + 2*dx[dir];
			int ty = y + 2*dy[dir];
			if (maze[ty][tx])
				dir = (dir+1) % 4;

			x += dx[dir];
			y += dy[dir];
		}
		for (int i = 2; i < n+2; ++i)
		{
			for (int j = 2; j < n+2; ++j)
				putchar(maze[i][j] ? '#' : ' ');
			putchar('\n');
		}
		if (d)
			putchar('\n');
	}

	return 0;
}
```