#include<iostream>
using namespace std;

#define N 100
#define rep(i, n) for(int i=0; i<n; ++i)

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

bool inRange(int x, int a, int b) {
	return a<=x && x<=b;
}

void drawSpiral(int n) {
	char mat[N][N];
	rep(i, n) rep(j, n) mat[i][j] = ' ';
	int x = 0, y = n-1, dir = 1, s = 0, mv = n;
	mat[y][x] = '#';
	while(1) {
		for(int i=0; i<mv-1; ++i) {
			x += dx[dir]; y += dy[dir];
			mat[y][x] = '#';
		}
		if(mv<=2 && s>0) break;
		if(s>0 && s%2==0) {
			mv -= 2;
			if(mv<=1) break;
		}
		dir = (dir + 1) % 4;
		++s;
	}
	rep(i, n) {
		rep(j, n) cout << mat[i][j];
		cout << endl;
	}
}

int main() {
	int d, n, count = 0;
	cin >> d;
	while(d--) {
		if(count++>0) cout << endl;
		cin >> n;
		drawSpiral(n);
	}
	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>
using namespace std;

#define N 100
#define rep(i, n) for(int i=0; i<n; ++i)

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

bool inRange(int x, int a, int b) {
	return a<=x && x<=b;
}

void drawSpiral(int n) {
	char mat[N][N];
	rep(i, n) rep(j, n) mat[i][j] = ' ';
	int x = 0, y = n-1, dir = 1, s = 0, mv = n;
	mat[y][x] = '#';
	while(1) {
		for(int i=0; i<mv-1; ++i) {
			x += dx[dir]; y += dy[dir];
			mat[y][x] = '#';
		}
		if(mv<=2 && s>0) break;
		if(s>0 && s%2==0) {
			mv -= 2;
			if(mv<=1) break;
		}
		dir = (dir + 1) % 4;
		++s;
	}
	rep(i, n) {
		rep(j, n) cout << mat[i][j];
		cout << endl;
	}
}

int main() {
	int d, n, count = 0;
	cin >> d;
	while(d--) {
		if(count++>0) cout << endl;
		cin >> n;
		drawSpiral(n);
	}
	return 0;
}
```