#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

#define EPS	1.0e-10
#define rep(idx, max)	for(int idx = 0, idx##Max = max; idx < idx##Max; idx ++)
#define rrep(idx, min, max)	for(int idx = min, idx##Max = max; idx < idx##Max; idx ++)
#define erep(idx, min, max)	for(int idx = min, idx##Max = max; idx <= idx##Max; idx ++)

#define rev(idx, max)	for(int idx = max - 1; idx >= 0; idx --)
#define MAX_N	128
char g_map[MAX_N][MAX_N];

int main()
{
	static int dx[] = { -1, 0, 1, 0 };
	static int dy[] = { 0, -1, 0, 1 };
	int dir;
	int edgeLen;
	int testCases;

	std::cin >> testCases;
	while (testCases -- > 0)
	{
		int x, y;
		std::cin >> edgeLen;
		::memset(g_map, ' ', sizeof(g_map));

		rep(y, edgeLen)
		{
			g_map[y][edgeLen] = '\0';
		}

		dir = 0;
		// ????????????????????????????????????????????????2????????????
		x = edgeLen + 2 - 1;
		y = edgeLen + 2 - 1;
		for (int n = edgeLen + 2; n >= 2; )
		{
			rep(i, n == 2 ? 1 : 2)
			{
				rep(j, n)
				{
					g_map[y][x] = '#';
					//::printf("(%d, %d)\n", x, y);
					x += dx[dir];
					y += dy[dir];
				}
				x -= dx[dir];
				y -= dy[dir];
				dir = (dir + 1) & 0x03;
			}
			n -= 2;
		}

		rep(y, edgeLen)
		{
			::puts(&g_map[y][0]);
		}
		if (testCases != 0) { ::puts(""); }
	}

	return(0);
}
### Prompt

Please create a solution in CPP 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 <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

#define EPS	1.0e-10
#define rep(idx, max)	for(int idx = 0, idx##Max = max; idx < idx##Max; idx ++)
#define rrep(idx, min, max)	for(int idx = min, idx##Max = max; idx < idx##Max; idx ++)
#define erep(idx, min, max)	for(int idx = min, idx##Max = max; idx <= idx##Max; idx ++)

#define rev(idx, max)	for(int idx = max - 1; idx >= 0; idx --)
#define MAX_N	128
char g_map[MAX_N][MAX_N];

int main()
{
	static int dx[] = { -1, 0, 1, 0 };
	static int dy[] = { 0, -1, 0, 1 };
	int dir;
	int edgeLen;
	int testCases;

	std::cin >> testCases;
	while (testCases -- > 0)
	{
		int x, y;
		std::cin >> edgeLen;
		::memset(g_map, ' ', sizeof(g_map));

		rep(y, edgeLen)
		{
			g_map[y][edgeLen] = '\0';
		}

		dir = 0;
		// ????????????????????????????????????????????????2????????????
		x = edgeLen + 2 - 1;
		y = edgeLen + 2 - 1;
		for (int n = edgeLen + 2; n >= 2; )
		{
			rep(i, n == 2 ? 1 : 2)
			{
				rep(j, n)
				{
					g_map[y][x] = '#';
					//::printf("(%d, %d)\n", x, y);
					x += dx[dir];
					y += dy[dir];
				}
				x -= dx[dir];
				y -= dy[dir];
				dir = (dir + 1) & 0x03;
			}
			n -= 2;
		}

		rep(y, edgeLen)
		{
			::puts(&g_map[y][0]);
		}
		if (testCases != 0) { ::puts(""); }
	}

	return(0);
}
```