#include <iostream>

struct Point {
	int x;
	int y;
	Point() {}
	Point(int x, int y) : x(x), y(y) {}
};

void show (char** a, int n)
{
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) std::cout << a[i][j];
		std::cout << std::endl;
	}
}

int main()
{
	int d; std::cin >> d;
	for (int k=0; k<d; k++) {
		int n; std::cin >> n;
		char** spiral = new char*[n];
		for (int i=0; i<n; i++) spiral[i] = new char[n];
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) spiral[i][j] = ' ';
		}
		
		Point p = Point(n-1, 0);
		int state = 0; // 0 : up, 1 : right, 2 : down, 3 : left
		bool finished = false;
		while (!finished) {
			spiral[p.x][p.y] = '#';
			switch (state) {
			case 0:
				if (p.x == 0 || (p.x >= 2 && spiral[p.x-2][p.y] == '#')) {
					if (n==1 || (n%4==1 && spiral[p.x][p.y+2] == '#')) {
						finished = true;
					}
					else state = 1;
				}
				else p.x--;
				break;
			case 1:
				if (p.y == n-1 || (p.y <= n-3 && spiral[p.x][p.y+2] == '#')) {
					if (n==2 || (n%4==2 && spiral[p.x+3][p.y] == '#')) {
						finished = true;
					}
					else state = 2;
				}
				else p.y++;
				break;
			case 2:
				if (p.x == n-1 || (p.x <= n-3 && spiral[p.x+2][p.y] == '#')) {
					if (n==3 || (n%4==3 && spiral[p.x][p.y-2] == '#')) {
						finished = true;
					}
					else state = 3;
				}
				else p.x++;
				break;
			case 3:
				if (spiral[p.x][p.y-2] == '#') {
					if (spiral[p.x-3][p.y] == '#') {
						finished = true;
					}
					else state = 0;
				}
				else p.y--;
				break;
			}
		}
		if (k>0) std::cout << std::endl;
		show(spiral, n);
		for (int i=0; i<n; i++) delete[] spiral[i];
		delete[] spiral;
	}
	
	return 0;
}



### Prompt

In cpp, your task is to solve 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>

struct Point {
	int x;
	int y;
	Point() {}
	Point(int x, int y) : x(x), y(y) {}
};

void show (char** a, int n)
{
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) std::cout << a[i][j];
		std::cout << std::endl;
	}
}

int main()
{
	int d; std::cin >> d;
	for (int k=0; k<d; k++) {
		int n; std::cin >> n;
		char** spiral = new char*[n];
		for (int i=0; i<n; i++) spiral[i] = new char[n];
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) spiral[i][j] = ' ';
		}
		
		Point p = Point(n-1, 0);
		int state = 0; // 0 : up, 1 : right, 2 : down, 3 : left
		bool finished = false;
		while (!finished) {
			spiral[p.x][p.y] = '#';
			switch (state) {
			case 0:
				if (p.x == 0 || (p.x >= 2 && spiral[p.x-2][p.y] == '#')) {
					if (n==1 || (n%4==1 && spiral[p.x][p.y+2] == '#')) {
						finished = true;
					}
					else state = 1;
				}
				else p.x--;
				break;
			case 1:
				if (p.y == n-1 || (p.y <= n-3 && spiral[p.x][p.y+2] == '#')) {
					if (n==2 || (n%4==2 && spiral[p.x+3][p.y] == '#')) {
						finished = true;
					}
					else state = 2;
				}
				else p.y++;
				break;
			case 2:
				if (p.x == n-1 || (p.x <= n-3 && spiral[p.x+2][p.y] == '#')) {
					if (n==3 || (n%4==3 && spiral[p.x][p.y-2] == '#')) {
						finished = true;
					}
					else state = 3;
				}
				else p.x++;
				break;
			case 3:
				if (spiral[p.x][p.y-2] == '#') {
					if (spiral[p.x-3][p.y] == '#') {
						finished = true;
					}
					else state = 0;
				}
				else p.y--;
				break;
			}
		}
		if (k>0) std::cout << std::endl;
		show(spiral, n);
		for (int i=0; i<n; i++) delete[] spiral[i];
		delete[] spiral;
	}
	
	return 0;
}



```