#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
using namespace std;

#define mk make_pair



int main(){
    int time;
    cin>>time;
    for(int p=0;p<time;p++){
    
    
        if(p!=0){cout<<endl;}
    int n;
    cin>>n;
    char a[1000][1000];
    fill(&a[0][0],&a[999][1000],' ');
    char t='u';
    a[n+99][100]='#';
    pair<int,int> w=mk(n+99,100);
        int j=0;
    while(j!=2){
        if(t=='u'){
            if(a[w.first-1][w.second]=='#'){break;}
            if(a[w.first-2][w.second]=='#' || w.first==100 || a[w.first-1][w.second+1]=='#'){t='r'; j++; continue;}
            w.first--;
        }
        if(t=='r'){
            if(a[w.first][w.second+1]=='#'){break;}
            if(a[w.first][w.second+2]=='#' || w.second==99+n || a[w.first+1][w.second+1]=='#'){t='d'; j++; continue;}
            w.second++;
        }
        if(t=='d'){
            if(a[w.first+1][w.second]=='#'){break;}
            if(a[w.first+2][w.second]=='#' || w.first==99+n || a[w.first+1][w.second-1]=='#'){t='l'; j++; continue;}
            w.first++;
        }
        if(t=='l'){
            if(a[w.first][w.second-1]=='#'){break;}
            if(a[w.first][w.second-2]=='#' || w.second==100 || a[w.first-1][w.second-1]=='#'){t='u'; j++; continue;}
            w.second--;
        }
        a[w.first][w.second]='#';
        j=0;
    }
    
    for(int i=100;i<n+100;i++){
        for(int t=100;t<n+100;t++){
            cout<<a[i][t];
        }
        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<stdio.h>
#include<math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
using namespace std;

#define mk make_pair



int main(){
    int time;
    cin>>time;
    for(int p=0;p<time;p++){
    
    
        if(p!=0){cout<<endl;}
    int n;
    cin>>n;
    char a[1000][1000];
    fill(&a[0][0],&a[999][1000],' ');
    char t='u';
    a[n+99][100]='#';
    pair<int,int> w=mk(n+99,100);
        int j=0;
    while(j!=2){
        if(t=='u'){
            if(a[w.first-1][w.second]=='#'){break;}
            if(a[w.first-2][w.second]=='#' || w.first==100 || a[w.first-1][w.second+1]=='#'){t='r'; j++; continue;}
            w.first--;
        }
        if(t=='r'){
            if(a[w.first][w.second+1]=='#'){break;}
            if(a[w.first][w.second+2]=='#' || w.second==99+n || a[w.first+1][w.second+1]=='#'){t='d'; j++; continue;}
            w.second++;
        }
        if(t=='d'){
            if(a[w.first+1][w.second]=='#'){break;}
            if(a[w.first+2][w.second]=='#' || w.first==99+n || a[w.first+1][w.second-1]=='#'){t='l'; j++; continue;}
            w.first++;
        }
        if(t=='l'){
            if(a[w.first][w.second-1]=='#'){break;}
            if(a[w.first][w.second-2]=='#' || w.second==100 || a[w.first-1][w.second-1]=='#'){t='u'; j++; continue;}
            w.second--;
        }
        a[w.first][w.second]='#';
        j=0;
    }
    
    for(int i=100;i<n+100;i++){
        for(int t=100;t<n+100;t++){
            cout<<a[i][t];
        }
        cout<<endl;
    }
        
        
        
    }
    
    
    return 0;
}

```