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

using namespace std;

int N, n;

char str[200][200];

void set_(int x, int y){
	if(x < 0 || y < 0 || x >= n || y >= n){
		return;
	}
	str[y][x] = ' ';
}

bool checker(int x, int y){
	if(x < 0 || y < 0 || x >= n || y >= n){
		return false;
	}
	if(str[y][x] == 'p'){
		return true;
	}
	return false;
}

bool set(int x, int y, int dx, int dy){
	if(x < 0 || y < 0 || x >= n || y >= n){
		return false;
	}
	if(str[y][x] != 'p'){
		return false;
	}
	str[y][x] = '#';
	if(dx != 0){
		if(checker(x - dx, y - 1)){
			set_(x - dx, y - 1);
		}
		if(checker(x - dx, y + 1)){
			set_(x - dx, y + 1);
		}
	}else{
		if(checker(x - 1, y - dy)){
			set_(x - 1, y - dy);
		}
		if(checker(x + 1, y - dy)){
			set_(x + 1, y - dy);
		}
	}
	if(!set(x + dx, y + dy, dx, dy)){
		if(dx > 0){
			dx = 0;
			dy = 1;
		}else if(dx < 0){
			dx = 0;
			dy = -1;
		}else if(dy > 0){
			dx = -1;
			dy = 0;
		}else{
			dx = 1;
			dy = 0;
		}
		set(x + dx, y + dy, dx, dy);
	}
	return true;
}

int main(){
	
	cin >> N;
	
	for(int loop = 0; loop < N; loop++){
		
		if(loop != 0){
			printf("\n");
		}
		
		cin >> n;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				str[i][j] = 'p';
			}
		}
		
		set(0, n - 1, 0, -1);
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(str[i][j] == 'p'){
					str[i][j] = ' ';
				}
			}
		}
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				printf("%c", str[i][j]);
			}
			printf("\n");
		}
	}
	
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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 <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int N, n;

char str[200][200];

void set_(int x, int y){
	if(x < 0 || y < 0 || x >= n || y >= n){
		return;
	}
	str[y][x] = ' ';
}

bool checker(int x, int y){
	if(x < 0 || y < 0 || x >= n || y >= n){
		return false;
	}
	if(str[y][x] == 'p'){
		return true;
	}
	return false;
}

bool set(int x, int y, int dx, int dy){
	if(x < 0 || y < 0 || x >= n || y >= n){
		return false;
	}
	if(str[y][x] != 'p'){
		return false;
	}
	str[y][x] = '#';
	if(dx != 0){
		if(checker(x - dx, y - 1)){
			set_(x - dx, y - 1);
		}
		if(checker(x - dx, y + 1)){
			set_(x - dx, y + 1);
		}
	}else{
		if(checker(x - 1, y - dy)){
			set_(x - 1, y - dy);
		}
		if(checker(x + 1, y - dy)){
			set_(x + 1, y - dy);
		}
	}
	if(!set(x + dx, y + dy, dx, dy)){
		if(dx > 0){
			dx = 0;
			dy = 1;
		}else if(dx < 0){
			dx = 0;
			dy = -1;
		}else if(dy > 0){
			dx = -1;
			dy = 0;
		}else{
			dx = 1;
			dy = 0;
		}
		set(x + dx, y + dy, dx, dy);
	}
	return true;
}

int main(){
	
	cin >> N;
	
	for(int loop = 0; loop < N; loop++){
		
		if(loop != 0){
			printf("\n");
		}
		
		cin >> n;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				str[i][j] = 'p';
			}
		}
		
		set(0, n - 1, 0, -1);
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(str[i][j] == 'p'){
					str[i][j] = ' ';
				}
			}
		}
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				printf("%c", str[i][j]);
			}
			printf("\n");
		}
	}
	
	return 0;
}
```