#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#define int long long
using namespace std;
int d, n;
char m[110][110];
signed main() {
	cin >> d;
	for (int v = 0; v < d; v++) {
		if (v)cout << endl;
		cin >> n;
		for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)m[i][j] = ' ';
		int x = -1, y = 0, p = n - 1, q = 0;
		while (1) {
			m[p][q] = '#';
			if (p + x < 0) {
				if (n == 1)break;
				x = 0; y = 1;
			}
			if (q + y >= n) {
				if (n == 2)break;
				x = 1; y = 0;
			}
			if (p + x >= n) {
				if (n == 3)break;
				x = 0; y = -1;
			}
			if (y == -1 && m[p][q - 2] == '#') {
				if (m[p - 1][q + 1] == '#')break;
				x = -1; y = 0;
				if (m[p - 2][q] == '#')break;
			}
			if (x == -1 && m[p - 2][q] == '#') {
				if (m[p + 1][q + 1] == '#')break;
				x = 0; y = 1;
				if (m[p][q + 2] == '#')break;
			}
			if (y == 1 && m[p][q + 2] == '#') {
				if (m[p + 1][q - 1] == '#')break;
				x = 1; y = 0;
				if (m[p + 2][q] == '#')break;
			}
			if (x == 1 && m[p + 2][q] == '#') {
				if (m[p - 1][q - 1] == '#')break;
				x = 0; y = -1;
				if (m[p][q - 2] == '#')break;
			}
			p += x; q += y;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)cout << m[i][j];
			cout << endl;
		}
	}
}

### Prompt

Create a solution in CPP for 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<algorithm>
#include<vector>
#include<string>
#define int long long
using namespace std;
int d, n;
char m[110][110];
signed main() {
	cin >> d;
	for (int v = 0; v < d; v++) {
		if (v)cout << endl;
		cin >> n;
		for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)m[i][j] = ' ';
		int x = -1, y = 0, p = n - 1, q = 0;
		while (1) {
			m[p][q] = '#';
			if (p + x < 0) {
				if (n == 1)break;
				x = 0; y = 1;
			}
			if (q + y >= n) {
				if (n == 2)break;
				x = 1; y = 0;
			}
			if (p + x >= n) {
				if (n == 3)break;
				x = 0; y = -1;
			}
			if (y == -1 && m[p][q - 2] == '#') {
				if (m[p - 1][q + 1] == '#')break;
				x = -1; y = 0;
				if (m[p - 2][q] == '#')break;
			}
			if (x == -1 && m[p - 2][q] == '#') {
				if (m[p + 1][q + 1] == '#')break;
				x = 0; y = 1;
				if (m[p][q + 2] == '#')break;
			}
			if (y == 1 && m[p][q + 2] == '#') {
				if (m[p + 1][q - 1] == '#')break;
				x = 1; y = 0;
				if (m[p + 2][q] == '#')break;
			}
			if (x == 1 && m[p + 2][q] == '#') {
				if (m[p - 1][q - 1] == '#')break;
				x = 0; y = -1;
				if (m[p][q - 2] == '#')break;
			}
			p += x; q += y;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)cout << m[i][j];
			cout << endl;
		}
	}
}

```