#include<vector>
#include<map>
#include<climits>
#include<set>
#include<queue>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<string>
#include<bitset>
#include<cstring>
#include<list>
using namespace std;
typedef vector<int>VI;
typedef vector<VI>VVI;
typedef vector<string>VS;
typedef pair<int,int>PII;
typedef long long LL;
typedef pair<LL,LL>PLL;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define PB push_back
#define EACH(i,c) for(typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define F first
#define S second

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

char fld[200][200];
int N;
void init(){
    fill(*fld,*fld+40000,' ');
    REP(i,N+4)fld[0][i]=fld[N+3][i]=fld[i][0]=fld[i][N+3]='#';
}

void solve(){
    int x=2,y=N+1,d=1;
    while(true){
        fld[y][x]='#';
        bool f2=false;
        REP(i,4){
            int nd=(d+i)%4;
            int ny=y+dy[nd];
            int nx=x+dx[nd];
            bool flag=true;
            REP(j,4){
                if(j==(nd+2)%4)continue;
                if(fld[ny+dy[j]][nx+dx[j]]=='#')flag=false;
            }
            if(flag){
                x=nx;
                y=ny;
                d=nd;
                f2=true;
                break;
            }

        }
        if(f2==false)return;
    }
}


int main(){
    int n;cin>>n;
    bool flag=false;
    while(n--){
        cin>>N;
        if(flag)cout<<endl;
        else flag=true;
        init();
        solve();
        if(N==2){
            cout<<"##"<<endl;
            cout<<"# "<<endl;
            continue;
        }
        FOR(i,2,N+2){
            FOR(j,2,N+2)cout<<fld[i][j];
            cout<<endl;
        }
    }

    return 0;
}
### Prompt

Please create a solution in Cpp 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<vector>
#include<map>
#include<climits>
#include<set>
#include<queue>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<string>
#include<bitset>
#include<cstring>
#include<list>
using namespace std;
typedef vector<int>VI;
typedef vector<VI>VVI;
typedef vector<string>VS;
typedef pair<int,int>PII;
typedef long long LL;
typedef pair<LL,LL>PLL;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define PB push_back
#define EACH(i,c) for(typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define F first
#define S second

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

char fld[200][200];
int N;
void init(){
    fill(*fld,*fld+40000,' ');
    REP(i,N+4)fld[0][i]=fld[N+3][i]=fld[i][0]=fld[i][N+3]='#';
}

void solve(){
    int x=2,y=N+1,d=1;
    while(true){
        fld[y][x]='#';
        bool f2=false;
        REP(i,4){
            int nd=(d+i)%4;
            int ny=y+dy[nd];
            int nx=x+dx[nd];
            bool flag=true;
            REP(j,4){
                if(j==(nd+2)%4)continue;
                if(fld[ny+dy[j]][nx+dx[j]]=='#')flag=false;
            }
            if(flag){
                x=nx;
                y=ny;
                d=nd;
                f2=true;
                break;
            }

        }
        if(f2==false)return;
    }
}


int main(){
    int n;cin>>n;
    bool flag=false;
    while(n--){
        cin>>N;
        if(flag)cout<<endl;
        else flag=true;
        init();
        solve();
        if(N==2){
            cout<<"##"<<endl;
            cout<<"# "<<endl;
            continue;
        }
        FOR(i,2,N+2){
            FOR(j,2,N+2)cout<<fld[i][j];
            cout<<endl;
        }
    }

    return 0;
}
```