#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
//#include <map>
#include <set>
#define INF (1000000000)
#define MOD (1000000007)
#define K (2)
using namespace std;

typedef vector<int> VI;
typedef vector<int>::iterator VII;
typedef vector<double> VD;
typedef vector<double>::iterator VDI;
typedef pair<int, int> PII;


char map[200][200];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};

int main()
{
	int num;
	scanf("%d", &num);
	for (int ca = 0; ca < num; ca++){
		for (int i = 0; i < 200; i++){
			strcpy(map[i], "");
		}
		
		int n;
		scanf("%d", &n);
		
		for (int i = 0; i < n + K + K; i++){
			for (int j = 0; j < n + K + K; j++){
				if (!i || !j || i == n + K + K - 1 || j == n + K + K - 1){
					map[i][j] = '#';
				}
				else {
					map[i][j] = ' ';
				}
			}
		}
		
		int y = n - 1 + K;
		int x = K;
		int d = 0;
		int nodraw = 0;
		while (true){
			int b = (d + 2) % 4;
			int r = (d + 1) % 4;
			if (map[y + dy[b]][x + dx[b]] != '#' || map[y + dy[r]][x + dx[r]] != '#'){
				map[y][x] = '#';
			}
			else {
				break;
			}
						
			if (map[y + dy[d] * 2][x + dx[d] * 2] == '#'){
				d = (d + 1) % 4;
				if (++nodraw == 4){
					break;
				}
			}
			else {
				y += dy[d];
				x += dx[d];
				nodraw = 0;
			}
		}
		
		if (ca) puts("");
		for (int i = 2; i < n + K; i++){
			printf("%.*s\n", n, &map[i][2]);
		}
	}
	
	return 0;
}
### Prompt

Create a solution in Cpp for 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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
//#include <map>
#include <set>
#define INF (1000000000)
#define MOD (1000000007)
#define K (2)
using namespace std;

typedef vector<int> VI;
typedef vector<int>::iterator VII;
typedef vector<double> VD;
typedef vector<double>::iterator VDI;
typedef pair<int, int> PII;


char map[200][200];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};

int main()
{
	int num;
	scanf("%d", &num);
	for (int ca = 0; ca < num; ca++){
		for (int i = 0; i < 200; i++){
			strcpy(map[i], "");
		}
		
		int n;
		scanf("%d", &n);
		
		for (int i = 0; i < n + K + K; i++){
			for (int j = 0; j < n + K + K; j++){
				if (!i || !j || i == n + K + K - 1 || j == n + K + K - 1){
					map[i][j] = '#';
				}
				else {
					map[i][j] = ' ';
				}
			}
		}
		
		int y = n - 1 + K;
		int x = K;
		int d = 0;
		int nodraw = 0;
		while (true){
			int b = (d + 2) % 4;
			int r = (d + 1) % 4;
			if (map[y + dy[b]][x + dx[b]] != '#' || map[y + dy[r]][x + dx[r]] != '#'){
				map[y][x] = '#';
			}
			else {
				break;
			}
						
			if (map[y + dy[d] * 2][x + dx[d] * 2] == '#'){
				d = (d + 1) % 4;
				if (++nodraw == 4){
					break;
				}
			}
			else {
				y += dy[d];
				x += dx[d];
				nodraw = 0;
			}
		}
		
		if (ca) puts("");
		for (int i = 2; i < n + K; i++){
			printf("%.*s\n", n, &map[i][2]);
		}
	}
	
	return 0;
}
```