#include <iostream>

#include <string>

using namespace std;

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

int main(){

	int d;

	cin >> d;

	for(int t = 0;t < d;t++){

		if(t) cout << endl;

		char s[102][102];

		int n;

		cin >> n;
		
		if(n == 1){
			cout << "#" << endl;
			continue;
			}

		for(int i = 0;i < n;i++){

			for(int j = 0;j < n;j++) s[i][j] = ' ';

		}

		int x = n - 1,y = 0,dir = 0;

		for(int k = 0;k < n;k++){

			bool flag = false;

			while(1){

				int nx = x + dx[dir],ny = y + dy[dir];

			 if(nx < 0 || nx >= n + 1 || ny < 0 || ny >= n + 1 || s[nx][ny] == '#') break;

s[x][y] = '#';

flag = true;

				x = nx;

				y = ny;

			}

if(x)x -= dx[dir];

if(y)y -= dy[dir];

			if(!flag) break;

			dir = (dir + 1) % 4;

		}

for(int i = 0;i < n;i++) {

for(int j = 0;j < n;j++){

cout << s[i][j];

}

cout << endl;}

	}

}
### Prompt

Your task is to create a cpp solution 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 <string>

using namespace std;

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

int main(){

	int d;

	cin >> d;

	for(int t = 0;t < d;t++){

		if(t) cout << endl;

		char s[102][102];

		int n;

		cin >> n;
		
		if(n == 1){
			cout << "#" << endl;
			continue;
			}

		for(int i = 0;i < n;i++){

			for(int j = 0;j < n;j++) s[i][j] = ' ';

		}

		int x = n - 1,y = 0,dir = 0;

		for(int k = 0;k < n;k++){

			bool flag = false;

			while(1){

				int nx = x + dx[dir],ny = y + dy[dir];

			 if(nx < 0 || nx >= n + 1 || ny < 0 || ny >= n + 1 || s[nx][ny] == '#') break;

s[x][y] = '#';

flag = true;

				x = nx;

				y = ny;

			}

if(x)x -= dx[dir];

if(y)y -= dy[dir];

			if(!flag) break;

			dir = (dir + 1) % 4;

		}

for(int i = 0;i < n;i++) {

for(int j = 0;j < n;j++){

cout << s[i][j];

}

cout << endl;}

	}

}
```