#include<iostream>
#include<algorithm>
#include<cstdio>

int main(){
	const int MAX_N = 100;
	const int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
	int d, n;

	std::cin >> d;
	for(int k=0;k<d;k++){
		std::cin >> n;

		if(k > 0){
			std::cout << std::endl;
		}

		if(n == 2){
			std::cout << "##\n# \n";
		}else{
			int x = 0, y = n-1, p = n-3, angle = 0;

			int cloth[MAX_N][MAX_N];
			for(int i=0;i<n;i++){
				std::fill(cloth[i], cloth[i]+n, 0);
			}
			
			for(int i=0;i<3;i++){
				cloth[y][x] = 1;
				for(int j=0;j<n-1;j++){
					x += dx[angle];
					y += dy[angle];
					cloth[y][x] = 1;
				}
				angle = (angle + 1) % 4;
			}
			
			while(p > 1){
				for(int i=0;i<2;i++){
					cloth[y][x] = 1;
					for(int j=0;j<p;j++){
						x += dx[angle];
						y += dy[angle];
						cloth[y][x] = 1;
					}
					angle = (angle + 1) % 4;						
				}
				p -= 2;
			}
			
			if(n % 2 == 0){//偶数
				x += dx[angle];
				y += dy[angle];
				cloth[y][x] = 1;
			}
			
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					if(cloth[i][j]){
						printf("#");
					}else{
						printf(" ");
					}
				}
				std::cout << std::endl;
			}
		}
	}
}
### Prompt

Your challenge is to write 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<algorithm>
#include<cstdio>

int main(){
	const int MAX_N = 100;
	const int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
	int d, n;

	std::cin >> d;
	for(int k=0;k<d;k++){
		std::cin >> n;

		if(k > 0){
			std::cout << std::endl;
		}

		if(n == 2){
			std::cout << "##\n# \n";
		}else{
			int x = 0, y = n-1, p = n-3, angle = 0;

			int cloth[MAX_N][MAX_N];
			for(int i=0;i<n;i++){
				std::fill(cloth[i], cloth[i]+n, 0);
			}
			
			for(int i=0;i<3;i++){
				cloth[y][x] = 1;
				for(int j=0;j<n-1;j++){
					x += dx[angle];
					y += dy[angle];
					cloth[y][x] = 1;
				}
				angle = (angle + 1) % 4;
			}
			
			while(p > 1){
				for(int i=0;i<2;i++){
					cloth[y][x] = 1;
					for(int j=0;j<p;j++){
						x += dx[angle];
						y += dy[angle];
						cloth[y][x] = 1;
					}
					angle = (angle + 1) % 4;						
				}
				p -= 2;
			}
			
			if(n % 2 == 0){//偶数
				x += dx[angle];
				y += dy[angle];
				cloth[y][x] = 1;
			}
			
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					if(cloth[i][j]){
						printf("#");
					}else{
						printf(" ");
					}
				}
				std::cout << std::endl;
			}
		}
	}
}
```