#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

int n;
char s[500][500];
int dx[]{ -1,0,1,0 }, dy[]{ 0,1,0,-1 };
struct st {
	int a, b, c;
};
int main() {
	int d; scanf("%d", &d);
	rep(i, d) {
		scanf("%d", &n);
		memset(s, 0, sizeof(s));
		rep(j, n)rep(k, n)s[j][k] = ' ';
		queue<st>que;
		s[n - 1][0] = '#';
		que.push({ n - 1, 0,0 });
		while (!que.empty()) {
			st p = que.front(); que.pop();
			int x = p.a, y = p.b, idx = p.c;
			int nx = x + dx[idx], ny = y + dy[idx];
			int kx = nx + dx[idx], ky = ny + dy[idx];
			int jx = nx + dx[(idx + 1) % 4], jy = ny + dy[(idx + 1) % 4];
			if (0 <= nx&&nx < n && 0 <= ny&&ny < n&&s[nx][ny] == ' ') {
				if (!(0 <= kx&&kx < n && 0 <= ky&&ky < n&&s[kx][ky] == '#') && !(0 <= jx&&jx < n && 0 <= jy&&jy < n&&s[jx][jy] == '#')) {
					s[nx][ny] = '#';
					que.push({ nx,ny,idx });
					continue;
				}
			}
			idx = (idx + 1) % 4;
			nx = x + dx[idx]; ny = y + dy[idx];
			kx = nx + dx[idx]; ky = ny + dy[idx];
			jx = nx + dx[(idx + 1) % 4]; jy = ny + dy[(idx + 1) % 4];
			if (0 <= nx&&nx < n && 0 <= ny&&ny < n&&s[nx][ny] == ' ') {
				if (!(0 <= kx&&kx < n && 0 <= ky&&ky < n&&s[kx][ky] == '#') && !(0 <= jx&&jx < n && 0 <= jy&&jy < n&&s[jx][jy] == '#')) {
					s[nx][ny] = '#';
					que.push({ nx,ny,idx });
				}
			}
		}
		rep(j, n)printf("%s\n", s[j]);
		if (i != d - 1)printf("\n");
	}
}
### 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<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

int n;
char s[500][500];
int dx[]{ -1,0,1,0 }, dy[]{ 0,1,0,-1 };
struct st {
	int a, b, c;
};
int main() {
	int d; scanf("%d", &d);
	rep(i, d) {
		scanf("%d", &n);
		memset(s, 0, sizeof(s));
		rep(j, n)rep(k, n)s[j][k] = ' ';
		queue<st>que;
		s[n - 1][0] = '#';
		que.push({ n - 1, 0,0 });
		while (!que.empty()) {
			st p = que.front(); que.pop();
			int x = p.a, y = p.b, idx = p.c;
			int nx = x + dx[idx], ny = y + dy[idx];
			int kx = nx + dx[idx], ky = ny + dy[idx];
			int jx = nx + dx[(idx + 1) % 4], jy = ny + dy[(idx + 1) % 4];
			if (0 <= nx&&nx < n && 0 <= ny&&ny < n&&s[nx][ny] == ' ') {
				if (!(0 <= kx&&kx < n && 0 <= ky&&ky < n&&s[kx][ky] == '#') && !(0 <= jx&&jx < n && 0 <= jy&&jy < n&&s[jx][jy] == '#')) {
					s[nx][ny] = '#';
					que.push({ nx,ny,idx });
					continue;
				}
			}
			idx = (idx + 1) % 4;
			nx = x + dx[idx]; ny = y + dy[idx];
			kx = nx + dx[idx]; ky = ny + dy[idx];
			jx = nx + dx[(idx + 1) % 4]; jy = ny + dy[(idx + 1) % 4];
			if (0 <= nx&&nx < n && 0 <= ny&&ny < n&&s[nx][ny] == ' ') {
				if (!(0 <= kx&&kx < n && 0 <= ky&&ky < n&&s[kx][ky] == '#') && !(0 <= jx&&jx < n && 0 <= jy&&jy < n&&s[jx][jy] == '#')) {
					s[nx][ny] = '#';
					que.push({ nx,ny,idx });
				}
			}
		}
		rep(j, n)printf("%s\n", s[j]);
		if (i != d - 1)printf("\n");
	}
}
```