#include <bits/stdc++.h>

using namespace std;

char MapData[100][100];
bool Finished;
int N;

bool check(int x, int y, int i) {
	 
	if (i == 0 || i==2) {
		if (MapData[y][x-1] == ' ' && MapData[y][x+1] == ' ') {
			return true;
		}
	}
	else if (i == 1 || i==3) {
		if (MapData[y-1][x] == ' ' && MapData[y+1][x] == ' ') {
			return true;
		}
	}
	return false;
}

void solve(int x, int y, int direction) {
	int dx[] = { 0,2,0,-2 };
	int dy[] = { -2,0,2,0 };
	int currentX, currentY, i, cnt;

	cnt = 0;
	for (i = direction; cnt < 4; i++) {
		currentX = x + dx[i%4];
		currentY = y + dy[i%4];
		if (currentX<0 || currentX>N-1 || currentY<0 || currentY>N-1) {
			continue;
		}
		if (MapData[currentY][currentX] == ' ') {
			switch (i%4)
			{
			case 0:currentY++; break;
			case 1:currentX--; break;
			case 2:currentY--; break;
			case 3:currentX++; break;
			}
			if (MapData[currentY][currentX] == ' ' && check(currentX, currentY, i%4)) {
				MapData[currentY][currentX] = '#';
				solve(currentX, currentY,i%4);
			}
		}
		if (Finished) {
			return;
		}
		cnt++;
	}
	if (cnt == 4) {
		Finished = true;
	}
}

int main() {
	int d;

	cin >> d;
	while (d--) {
		cin >> N;

		memset(MapData, ' ', sizeof(MapData));
		Finished = false;
		for (int i = 0; i < N; i++) {
			MapData[0][i] = '#';
			MapData[i][0] = MapData[i][N - 1] = '#';
			MapData[N - 1][i] = '#';
		}
		if (N > 1) {
			MapData[N - 1][1] = ' ';
		}
		if (N > 4) {
			solve(2, N - 1, 0);
		}


		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << MapData[i][j];
			}
			cout << endl;
		}
		if (d != 0) {
			cout << endl;
		}
	}

	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 <bits/stdc++.h>

using namespace std;

char MapData[100][100];
bool Finished;
int N;

bool check(int x, int y, int i) {
	 
	if (i == 0 || i==2) {
		if (MapData[y][x-1] == ' ' && MapData[y][x+1] == ' ') {
			return true;
		}
	}
	else if (i == 1 || i==3) {
		if (MapData[y-1][x] == ' ' && MapData[y+1][x] == ' ') {
			return true;
		}
	}
	return false;
}

void solve(int x, int y, int direction) {
	int dx[] = { 0,2,0,-2 };
	int dy[] = { -2,0,2,0 };
	int currentX, currentY, i, cnt;

	cnt = 0;
	for (i = direction; cnt < 4; i++) {
		currentX = x + dx[i%4];
		currentY = y + dy[i%4];
		if (currentX<0 || currentX>N-1 || currentY<0 || currentY>N-1) {
			continue;
		}
		if (MapData[currentY][currentX] == ' ') {
			switch (i%4)
			{
			case 0:currentY++; break;
			case 1:currentX--; break;
			case 2:currentY--; break;
			case 3:currentX++; break;
			}
			if (MapData[currentY][currentX] == ' ' && check(currentX, currentY, i%4)) {
				MapData[currentY][currentX] = '#';
				solve(currentX, currentY,i%4);
			}
		}
		if (Finished) {
			return;
		}
		cnt++;
	}
	if (cnt == 4) {
		Finished = true;
	}
}

int main() {
	int d;

	cin >> d;
	while (d--) {
		cin >> N;

		memset(MapData, ' ', sizeof(MapData));
		Finished = false;
		for (int i = 0; i < N; i++) {
			MapData[0][i] = '#';
			MapData[i][0] = MapData[i][N - 1] = '#';
			MapData[N - 1][i] = '#';
		}
		if (N > 1) {
			MapData[N - 1][1] = ' ';
		}
		if (N > 4) {
			solve(2, N - 1, 0);
		}


		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << MapData[i][j];
			}
			cout << endl;
		}
		if (d != 0) {
			cout << endl;
		}
	}

	return 0;
}


```