#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<(o)<<" ";}
#define dumpl(o) if(DBG){cerr<<#o<<" "<<(o)<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
int N;
bool inrange(int i, int j) { return 0 <= i&&i < N && 0 <= j&&j < N; }

signed main() {
	int d; cin >> d;
	int a[120][120] = {};
	int di[] = { -1,0,1,0 };
	int dj[] = { 0,1,0,-1 };
	rep(h, 0, d) {
		if (h != 0)cout << endl;
		memset(a, 0, sizeof(a));
		cin >> N;

		if (N == 1) { cout << "#" << endl; continue; }
		if (N == 2) { cout << "##" << endl << "# " << endl; continue; }

		int ci = N - 1, cj = 0;
		int dir = 0;
		int cnt = 1;
		while (true) {
			a[ci][cj] = cnt;
			int ni = ci + di[dir], nj = cj + dj[dir];
			if (!inrange(ni, nj)) {
				dir = (dir + 1) % 4;
				ni = ci + di[dir], nj = cj + dj[dir];
			}
			else if (inrange(ni + di[dir], nj + dj[dir]) && a[ni + di[dir]][nj + dj[dir]] != 0) {
				dir = (dir + 1) % 4;
				ni = ci + di[dir], nj = cj + dj[dir];
			}
			dump(ci)dumpl(cj);
			dump(ni + dj[dir])dumpl(nj + dj[dir]);
			if (inrange(ni + di[dir], nj + dj[dir]) && (a[ni + di[dir]][nj + dj[dir]] != 0 || a[ni + di[(dir + 1) % 4]][nj + dj[(dir + 1) % 4]] != 0)) {
				break;
			}
			ci += di[dir];
			cj += dj[dir];

		}
		rep(i, 0, N) {
			rep(j, 0, N) {
				cout << (a[i][j] ? '#' : ' ');
			}
			cout << endl;
		}
	}
	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 "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<(o)<<" ";}
#define dumpl(o) if(DBG){cerr<<#o<<" "<<(o)<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
int N;
bool inrange(int i, int j) { return 0 <= i&&i < N && 0 <= j&&j < N; }

signed main() {
	int d; cin >> d;
	int a[120][120] = {};
	int di[] = { -1,0,1,0 };
	int dj[] = { 0,1,0,-1 };
	rep(h, 0, d) {
		if (h != 0)cout << endl;
		memset(a, 0, sizeof(a));
		cin >> N;

		if (N == 1) { cout << "#" << endl; continue; }
		if (N == 2) { cout << "##" << endl << "# " << endl; continue; }

		int ci = N - 1, cj = 0;
		int dir = 0;
		int cnt = 1;
		while (true) {
			a[ci][cj] = cnt;
			int ni = ci + di[dir], nj = cj + dj[dir];
			if (!inrange(ni, nj)) {
				dir = (dir + 1) % 4;
				ni = ci + di[dir], nj = cj + dj[dir];
			}
			else if (inrange(ni + di[dir], nj + dj[dir]) && a[ni + di[dir]][nj + dj[dir]] != 0) {
				dir = (dir + 1) % 4;
				ni = ci + di[dir], nj = cj + dj[dir];
			}
			dump(ci)dumpl(cj);
			dump(ni + dj[dir])dumpl(nj + dj[dir]);
			if (inrange(ni + di[dir], nj + dj[dir]) && (a[ni + di[dir]][nj + dj[dir]] != 0 || a[ni + di[(dir + 1) % 4]][nj + dj[(dir + 1) % 4]] != 0)) {
				break;
			}
			ci += di[dir];
			cj += dj[dir];

		}
		rep(i, 0, N) {
			rep(j, 0, N) {
				cout << (a[i][j] ? '#' : ' ');
			}
			cout << endl;
		}
	}
	return 0;
}
```