#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cctype>
#include <sstream>
#include <algorithm>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for (iter(c) it=(c).begin(); it!=(c).end(); it++)
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define pr(a) cout << (a) << endl
typedef long long ll;
typedef pair<int,int> P;
const int MAX=1000000000;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int main() {
  int t;
  cin >> t;
  bool ck=false;
  while(t--) {
    if(ck) cout << endl;
    ck=true;
    int n;
    cin >> n;
    string s[n][n];
    bool d[n][n];
    rep(i,n) {
      rep(j,n) {
	if(i==0 || j==0 || j==n-1) s[i][j]='#';
	else s[i][j]=' ';
	if(i==n-1 && j==n-1 && n!=1) s[i][j]=' ';
	d[i][j]=false;
	if(i==1 && j>=1 || j==1 && i>=1 || j==n-2 && i>=1 && i<n-1) d[i][j]=true;
      }
    }
    if(n<=2) {
      rep(i,n) {
	rep(j,n) cout << s[i][j];
	cout << endl;
      }
      continue;
    }
    int nx=n-1,ny=n-1,k=3,kk=0;
    while(1) {
      s[nx][ny]='#';
      if(d[nx+dx[k]][ny+dy[k]]) {
	k=(k+1)%4;
	kk=(kk+1)%4;
	if(d[nx+dx[k]][ny+dy[k]]) break;
      }
      d[nx+dx[kk]][ny+dy[kk]]=true;
      nx+=dx[k];
      ny+=dy[k];
    }
    rep(i,n) {
      rep(j,n) cout << s[i][j];
      cout << endl;
    }
  }
  return 0;
}

### Prompt

Please formulate 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 <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cctype>
#include <sstream>
#include <algorithm>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for (iter(c) it=(c).begin(); it!=(c).end(); it++)
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define pr(a) cout << (a) << endl
typedef long long ll;
typedef pair<int,int> P;
const int MAX=1000000000;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int main() {
  int t;
  cin >> t;
  bool ck=false;
  while(t--) {
    if(ck) cout << endl;
    ck=true;
    int n;
    cin >> n;
    string s[n][n];
    bool d[n][n];
    rep(i,n) {
      rep(j,n) {
	if(i==0 || j==0 || j==n-1) s[i][j]='#';
	else s[i][j]=' ';
	if(i==n-1 && j==n-1 && n!=1) s[i][j]=' ';
	d[i][j]=false;
	if(i==1 && j>=1 || j==1 && i>=1 || j==n-2 && i>=1 && i<n-1) d[i][j]=true;
      }
    }
    if(n<=2) {
      rep(i,n) {
	rep(j,n) cout << s[i][j];
	cout << endl;
      }
      continue;
    }
    int nx=n-1,ny=n-1,k=3,kk=0;
    while(1) {
      s[nx][ny]='#';
      if(d[nx+dx[k]][ny+dy[k]]) {
	k=(k+1)%4;
	kk=(kk+1)%4;
	if(d[nx+dx[k]][ny+dy[k]]) break;
      }
      d[nx+dx[kk]][ny+dy[kk]]=true;
      nx+=dx[k];
      ny+=dy[k];
    }
    rep(i,n) {
      rep(j,n) cout << s[i][j];
      cout << endl;
    }
  }
  return 0;
}

```