#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <complex>

#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define tr(c, i) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define rtr(c, i) for (typeof((c).rbegin()) i = (c).rbegin(); i != (c).rend(); --i)
#define contains(c, x) ((c).find(x) != (c).end())
#define Contains(c, x) (find(all(c), x) != (c).end())
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) REP(i, 0, (n))
#define To_String to_string< char,std::char_traits<char>,std::allocator<char> >

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int dr[] = { -1, 0, 1, 0 }, dc[] = { 0, 1, 0, -1 };
int a[110][110];
int main()
{
	ios_base::sync_with_stdio(0);
	int d; cin >> d;
	while (d--) {
		int n; cin >> n;
		int cnt = n;
		if (n % 2 == 0) {
			for (int i=1; n-i>1; i+=2) cnt += 2*(n-i);
			cnt++;
		}
		else {
			for (int i=1; n-i>1; i+=2) cnt += 2*(n-i);
		}
		memset(a, 0, sizeof(a));
		int r = n, c = 1, k = 0, x = 0;
		while (x < cnt) {
			a[r][c] = ++x;
			r += dr[k], c += dc[k];
			if (r <= 0 || r >= n+1 || c <= 0 || c >= n+1) {
				r -= dr[k], c -= dc[k];
				k = (k + 1) % 4;
				r += dr[k], c += dc[k];
			}
			else if (a[r+dr[k]][c+dc[k]]) {
				a[r][c] = 0;
				r -= dr[k], c -= dc[k];
				k = (k + 1) % 4;
				r += dr[k], c += dc[k];
			}
		}
		REP(i, 1, n+1) {
			REP(j, 1, n+1) putchar(a[i][j] ? '#' : ' ');
			//REP(j, 1, n+1) printf("%3d", a[i][j]);
			puts("");
		}
		if (d) puts("");
	}
	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 <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <complex>

#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define tr(c, i) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define rtr(c, i) for (typeof((c).rbegin()) i = (c).rbegin(); i != (c).rend(); --i)
#define contains(c, x) ((c).find(x) != (c).end())
#define Contains(c, x) (find(all(c), x) != (c).end())
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) REP(i, 0, (n))
#define To_String to_string< char,std::char_traits<char>,std::allocator<char> >

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int dr[] = { -1, 0, 1, 0 }, dc[] = { 0, 1, 0, -1 };
int a[110][110];
int main()
{
	ios_base::sync_with_stdio(0);
	int d; cin >> d;
	while (d--) {
		int n; cin >> n;
		int cnt = n;
		if (n % 2 == 0) {
			for (int i=1; n-i>1; i+=2) cnt += 2*(n-i);
			cnt++;
		}
		else {
			for (int i=1; n-i>1; i+=2) cnt += 2*(n-i);
		}
		memset(a, 0, sizeof(a));
		int r = n, c = 1, k = 0, x = 0;
		while (x < cnt) {
			a[r][c] = ++x;
			r += dr[k], c += dc[k];
			if (r <= 0 || r >= n+1 || c <= 0 || c >= n+1) {
				r -= dr[k], c -= dc[k];
				k = (k + 1) % 4;
				r += dr[k], c += dc[k];
			}
			else if (a[r+dr[k]][c+dc[k]]) {
				a[r][c] = 0;
				r -= dr[k], c -= dc[k];
				k = (k + 1) % 4;
				r += dr[k], c += dc[k];
			}
		}
		REP(i, 1, n+1) {
			REP(j, 1, n+1) putchar(a[i][j] ? '#' : ' ');
			//REP(j, 1, n+1) printf("%3d", a[i][j]);
			puts("");
		}
		if (d) puts("");
	}
	return 0;
}
```