#include <stdio.h>
#include <stack>
#include <math.h>

using namespace std;

int n;

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= n-1 && col >= 0 && col <= n-1)return true;
	else{
		return false;
	}
}

int main(){

	int d,row,col,move;
	char current,table[100][101];
	bool FLG,First = true;

	scanf("%d",&d);

	for(int loop=0; loop < d; loop++){
		scanf("%d",&n);


		if(!First)printf("\n");

		for(int i=0; i < n; i++){
			for(int k=0; k < n; k++)table[i][k] = ' ';
		}

		row = n-1,col = 0;
		current = 'U';

		FLG = true;

		while(FLG){
			move = 0;

			switch(current){
			case 'U':

				for(;row >= 0; row--){
					if((rangeCheck(row-1,col) == true && table[row-1][col] == '#')||
					   (rangeCheck(row,col-1) == true && table[row][col-1] == '#')||
					   (rangeCheck(row,col+1) == true && table[row][col+1] == '#'))break;

					table[row][col] = '#';
					move++;
				}
				if(move == 0){
					FLG = false;
				}else{
					row += 1;
					col += 1;
					current = 'R';
				}
				break;
			case 'R':

				for(;col <= n-1; col++){
					if((rangeCheck(row-1,col) == true && table[row-1][col] == '#')||
					   (rangeCheck(row+1,col) == true && table[row+1][col] == '#')||
					   (rangeCheck(row,col+1) == true && table[row][col+1] == '#'))break;

					table[row][col] = '#';
					move++;
				}
				if(move == 0){
					FLG =false;
				}else{
					col -= 1;
					row += 1;
					current = 'D';
				}
				break;
			case 'D':

				for(; row <= n-1; row++){
					if((rangeCheck(row,col-1) == true && table[row][col-1] == '#')||
					   (rangeCheck(row+1,col) == true && table[row+1][col] == '#')||
					   (rangeCheck(row,col+1) == true && table[row][col+1] == '#'))break;

					table[row][col] = '#';
					move++;
				}
				if(move == 0){
					FLG = false;
				}else{
					row -= 1;
					col -= 1;
					current = 'L';
				}
				break;
			case 'L':

				for(; col >= 0; col--){
					if((rangeCheck(row-1,col) == true && table[row-1][col] == '#')||
					   (rangeCheck(row+1,col) == true && table[row+1][col] == '#')||
					   (rangeCheck(row,col-1) == true && table[row][col-1] == '#'))break;

					table[row][col] = '#';
					move++;
				}
				if(move == 0){
					FLG = false;
				}else{
					col += 1;
					row -= 1;
					current = 'U';
				}
				break;
			}
		}

		for(int i=0; i < n; i++){
			for(int k=0; k < n; k++)printf("%c",table[i][k]);
			printf("\n");
		}

		if(First)First = false;

	}


    return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <stdio.h>
#include <stack>
#include <math.h>

using namespace std;

int n;

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= n-1 && col >= 0 && col <= n-1)return true;
	else{
		return false;
	}
}

int main(){

	int d,row,col,move;
	char current,table[100][101];
	bool FLG,First = true;

	scanf("%d",&d);

	for(int loop=0; loop < d; loop++){
		scanf("%d",&n);


		if(!First)printf("\n");

		for(int i=0; i < n; i++){
			for(int k=0; k < n; k++)table[i][k] = ' ';
		}

		row = n-1,col = 0;
		current = 'U';

		FLG = true;

		while(FLG){
			move = 0;

			switch(current){
			case 'U':

				for(;row >= 0; row--){
					if((rangeCheck(row-1,col) == true && table[row-1][col] == '#')||
					   (rangeCheck(row,col-1) == true && table[row][col-1] == '#')||
					   (rangeCheck(row,col+1) == true && table[row][col+1] == '#'))break;

					table[row][col] = '#';
					move++;
				}
				if(move == 0){
					FLG = false;
				}else{
					row += 1;
					col += 1;
					current = 'R';
				}
				break;
			case 'R':

				for(;col <= n-1; col++){
					if((rangeCheck(row-1,col) == true && table[row-1][col] == '#')||
					   (rangeCheck(row+1,col) == true && table[row+1][col] == '#')||
					   (rangeCheck(row,col+1) == true && table[row][col+1] == '#'))break;

					table[row][col] = '#';
					move++;
				}
				if(move == 0){
					FLG =false;
				}else{
					col -= 1;
					row += 1;
					current = 'D';
				}
				break;
			case 'D':

				for(; row <= n-1; row++){
					if((rangeCheck(row,col-1) == true && table[row][col-1] == '#')||
					   (rangeCheck(row+1,col) == true && table[row+1][col] == '#')||
					   (rangeCheck(row,col+1) == true && table[row][col+1] == '#'))break;

					table[row][col] = '#';
					move++;
				}
				if(move == 0){
					FLG = false;
				}else{
					row -= 1;
					col -= 1;
					current = 'L';
				}
				break;
			case 'L':

				for(; col >= 0; col--){
					if((rangeCheck(row-1,col) == true && table[row-1][col] == '#')||
					   (rangeCheck(row+1,col) == true && table[row+1][col] == '#')||
					   (rangeCheck(row,col-1) == true && table[row][col-1] == '#'))break;

					table[row][col] = '#';
					move++;
				}
				if(move == 0){
					FLG = false;
				}else{
					col += 1;
					row -= 1;
					current = 'U';
				}
				break;
			}
		}

		for(int i=0; i < n; i++){
			for(int k=0; k < n; k++)printf("%c",table[i][k]);
			printf("\n");
		}

		if(First)First = false;

	}


    return 0;
}
```