#include <iostream>
using namespace std;

void draw(int n){
  int m[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
  int t=0, muki=0, x=n+1, y=2;
  int cn[n+4][n+4];
  for(int i=1; i<n+3; i++)
    for(int j=1; j<n+3; j++)
      cn[i][j]=0;
  for(int i=0; i<n+4; i++){
    cn[i][0]=1;
    cn[i][n+3]=1;
    cn[0][i]=1;
    cn[n+3][i]=1;
  }

  while(t<2){
    if(t==1){
      if(cn[x+m[muki%4][0]+m[(muki+1)%4][0]][y+m[muki%4][1]+m[(muki+1)%4][1]]==1)
	break;
    }
    if(cn[x+2*m[muki%4][0]][y+2*m[muki%4][1]]==1)
      {t++; muki++; cn[x][y]=1;}
    else{
      t = 0;
      cn[x][y]=1;
      x+=m[muki%4][0];
      y+=m[muki%4][1];
    }
  }
  
  for(int i=2; i<n+2; i++){
    for(int j=2; j<n+2; j++){
      if(cn[i][j]==1)
	cout << "#";
      else
	cout << " ";
    }
    cout << endl;
  }
}

int main(){
  int d, n;
  cin >> d;

  for(int i=0; i<d-1; i++){
    cin >> n;
    draw(n);
    cout << endl;
  }
  cin >> n;
  draw(n);
  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 <iostream>
using namespace std;

void draw(int n){
  int m[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
  int t=0, muki=0, x=n+1, y=2;
  int cn[n+4][n+4];
  for(int i=1; i<n+3; i++)
    for(int j=1; j<n+3; j++)
      cn[i][j]=0;
  for(int i=0; i<n+4; i++){
    cn[i][0]=1;
    cn[i][n+3]=1;
    cn[0][i]=1;
    cn[n+3][i]=1;
  }

  while(t<2){
    if(t==1){
      if(cn[x+m[muki%4][0]+m[(muki+1)%4][0]][y+m[muki%4][1]+m[(muki+1)%4][1]]==1)
	break;
    }
    if(cn[x+2*m[muki%4][0]][y+2*m[muki%4][1]]==1)
      {t++; muki++; cn[x][y]=1;}
    else{
      t = 0;
      cn[x][y]=1;
      x+=m[muki%4][0];
      y+=m[muki%4][1];
    }
  }
  
  for(int i=2; i<n+2; i++){
    for(int j=2; j<n+2; j++){
      if(cn[i][j]==1)
	cout << "#";
      else
	cout << " ";
    }
    cout << endl;
  }
}

int main(){
  int d, n;
  cin >> d;

  for(int i=0; i<d-1; i++){
    cin >> n;
    draw(n);
    cout << endl;
  }
  cin >> n;
  draw(n);
  return 0;
}
```