#include<iostream>
using namespace std;
char t[100][100];
int n,a,x,y,d,ny,nx,flg,cnt;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};

void rec(int y,int x,int d){

  
  /*
    for(int i=0;i<a;i++){
      for(int j=0;j<a;j++){
	cout<<t[i][j];
      }
      cout<<endl;
    }

    cout<<y<<' '<<x<<' '<<d<<endl;*/
  cnt=0;
  for(int i=0;i<a;i++){
    t[y][x]='#';cnt++;
    ny=y+dy[d]*2;
    nx=x+dx[d]*2;
    if(t[ny][nx]=='#'){
      break;
    }
    y=y+dy[d];
    x=x+dx[d];
  }
  if(cnt>=3)rec(y,x,(d+1)%4);
}

int main(){
  cin>>n;
  while(n--){
    cin>>a;
    if(a==1){
      cout<<'#'<<endl;
          if(n>=1)cout<<endl;
      continue;
    }else if(a==2){
      cout<<"##"<<endl;
      cout<<"# "<<endl;
    if(n>=1)cout<<endl;
      continue;
    }else if(a==4){
      cout<<"####"<<endl;
      cout<<"#  #"<<endl;
      cout<<"#  #"<<endl;
      cout<<"# ##"<<endl;
    if(n>=1)cout<<endl;
      continue;
    }

    for(int i=0;i<100;i++)
      for(int j=0;j<100;j++)
	t[i][j]=' ';
    
    t[a-1][0]=' ';
    x=0;y=a-1;
    
    for(int i=0;i<a;i++){
      t[a-1][i]=t[i][a-1]='#';
      t[0][i]=t[i][0]='#';
    }
    t[a-1][1]=' ';
    
    rec(a-1,2,0);
    



    for(int i=0;i<a;i++){
      for(int j=0;j<a;j++){
	cout<<t[i][j];
      }
      cout<<endl;
    }
    if(n>=1)cout<<endl;
  }
  return 0;
}
### Prompt

Your task is to create 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>
using namespace std;
char t[100][100];
int n,a,x,y,d,ny,nx,flg,cnt;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};

void rec(int y,int x,int d){

  
  /*
    for(int i=0;i<a;i++){
      for(int j=0;j<a;j++){
	cout<<t[i][j];
      }
      cout<<endl;
    }

    cout<<y<<' '<<x<<' '<<d<<endl;*/
  cnt=0;
  for(int i=0;i<a;i++){
    t[y][x]='#';cnt++;
    ny=y+dy[d]*2;
    nx=x+dx[d]*2;
    if(t[ny][nx]=='#'){
      break;
    }
    y=y+dy[d];
    x=x+dx[d];
  }
  if(cnt>=3)rec(y,x,(d+1)%4);
}

int main(){
  cin>>n;
  while(n--){
    cin>>a;
    if(a==1){
      cout<<'#'<<endl;
          if(n>=1)cout<<endl;
      continue;
    }else if(a==2){
      cout<<"##"<<endl;
      cout<<"# "<<endl;
    if(n>=1)cout<<endl;
      continue;
    }else if(a==4){
      cout<<"####"<<endl;
      cout<<"#  #"<<endl;
      cout<<"#  #"<<endl;
      cout<<"# ##"<<endl;
    if(n>=1)cout<<endl;
      continue;
    }

    for(int i=0;i<100;i++)
      for(int j=0;j<100;j++)
	t[i][j]=' ';
    
    t[a-1][0]=' ';
    x=0;y=a-1;
    
    for(int i=0;i<a;i++){
      t[a-1][i]=t[i][a-1]='#';
      t[0][i]=t[i][0]='#';
    }
    t[a-1][1]=' ';
    
    rec(a-1,2,0);
    



    for(int i=0;i<a;i++){
      for(int j=0;j<a;j++){
	cout<<t[i][j];
      }
      cout<<endl;
    }
    if(n>=1)cout<<endl;
  }
  return 0;
}
```