#include <bits/stdc++.h>

using namespace std;
 
#define MAX 150
 
char sp[MAX][MAX];
//u r d l
const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};
 
bool range(int x, int y, int n)
{
    if (0 > x || x >= n || 0 > y || y >= n) {
	return 0;
    }
    return 1;
}
 
void make(int n)
{
    int x = 0, y = n-1, dir = 0;
 
    for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	    sp[i][j] = '.';
	}
    }
    int end = 0;
    sp[y][x] = '#';
    while (1) {
	int nx = x + dx[dir];
	int ny = y + dy[dir];  
 
	bool flg = 1;
	if (!range(nx, ny, n)) {
	    flg = 0;
	}
 
	for (int i = 0; i < 4; i++) {
	    int nnx = nx + dx[i];
	    int nny = ny + dy[i];
 
	    if ((x == nnx && y == nny) 
	       || !range(nnx, nny, n)) {
		continue;
	    }
 
	    if (sp[nny][nnx] == '#') {
		flg = 0;
		break;
	    }
	}
 
	if (!flg) {
	    dir++;
	    dir = dir % 4;
	    end++;
	    if (end == 4) return;
	} else {
	    end = 0;
	}
 
	if (flg) {
	    sp[ny][nx] = '#';
	    x = nx;
	    y = ny;
	}
    }
}
 
int main()
{
    int d, n;
    bool ok = 0;
 
    scanf("%d", &d);
    while (d--) {
	scanf("%d", &n);
 
	if (ok) {
	    puts("");
	}
	ok = 1;
	make(n);
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		if (sp[i][j] == '.') {
		    printf(" ");
		} else {
		    printf("%c", sp[i][j]);
		}
	    }
	    puts("");
	}   
    }
    return 0;
}
### 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 <bits/stdc++.h>

using namespace std;
 
#define MAX 150
 
char sp[MAX][MAX];
//u r d l
const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};
 
bool range(int x, int y, int n)
{
    if (0 > x || x >= n || 0 > y || y >= n) {
	return 0;
    }
    return 1;
}
 
void make(int n)
{
    int x = 0, y = n-1, dir = 0;
 
    for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	    sp[i][j] = '.';
	}
    }
    int end = 0;
    sp[y][x] = '#';
    while (1) {
	int nx = x + dx[dir];
	int ny = y + dy[dir];  
 
	bool flg = 1;
	if (!range(nx, ny, n)) {
	    flg = 0;
	}
 
	for (int i = 0; i < 4; i++) {
	    int nnx = nx + dx[i];
	    int nny = ny + dy[i];
 
	    if ((x == nnx && y == nny) 
	       || !range(nnx, nny, n)) {
		continue;
	    }
 
	    if (sp[nny][nnx] == '#') {
		flg = 0;
		break;
	    }
	}
 
	if (!flg) {
	    dir++;
	    dir = dir % 4;
	    end++;
	    if (end == 4) return;
	} else {
	    end = 0;
	}
 
	if (flg) {
	    sp[ny][nx] = '#';
	    x = nx;
	    y = ny;
	}
    }
}
 
int main()
{
    int d, n;
    bool ok = 0;
 
    scanf("%d", &d);
    while (d--) {
	scanf("%d", &n);
 
	if (ok) {
	    puts("");
	}
	ok = 1;
	make(n);
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		if (sp[i][j] == '.') {
		    printf(" ");
		} else {
		    printf("%c", sp[i][j]);
		}
	    }
	    puts("");
	}   
    }
    return 0;
}
```