#include <bits/stdc++.h>

using namespace std;

int N;
int MX;
char output[500][500];

void PRINT() {
  for(int i=0; i<MX; i++) {
    cout << output[i] << endl;
  }
}

int main() {
  
  int Tc; cin >> Tc;
  bool blank = 0;
  while(Tc--) {
    if(blank) cout << endl;
    blank = 1;
    
    cin >> N;
    MX = N;
     
    for(int i=0; i<N; i++) {
      for(int j=0; j<N; j++) {
	output[i][j] = ' ';
      }
    }
    
    for(int i=0; i<N; i++) output[i][N] = 0;
    
    int cnt = 0;
    
    //////////////// phase 1 START
    
    int x = 0, y = N-1;
    for(int i=0; i<N; i++) {
      output[y-i][x] = '#';
    }
    y -= N-1;
    cnt ++;
    if(cnt == MX) goto EXIT;
        
    for(int i=0; i<N; i++) {
      output[y][x+i] = '#';
    }
    x += N-1;
    cnt ++;
    if(cnt == MX) goto EXIT;
    
    for(int i=0; i<N; i++) {
      output[y+i][x] = '#';
    }
    y += N-1;
    cnt ++;

    if(cnt == MX) goto EXIT;
    
    //////////////// phase 1 END
    
    
    //////////////// phase 2 START
    
    while(1) {
      
      N -= 2;
      for(int i=0; i<N; i++) {
	output[y][x-i] = '#';
      }
      
      x -= N-1;
      cnt ++;
      if(cnt == MX) goto EXIT;
      
      for(int i=0; i<N; i++) {
	output[y-i][x] = '#';
      }
      y -= N-1;
      cnt ++;
      if(cnt == MX) goto EXIT;
      
      N -= 2;
      
      for(int i=0; i<N; i++) {
	output[y][x+i] = '#';
      }
      x += N-1;
      cnt ++;
      if(cnt == MX) goto EXIT;
      
      for(int i=0; i<N; i++) {
	output[y+i][x] = '#';
      }
      y += N-1;
      cnt ++;
      if(cnt == MX) goto EXIT;
    }
    //////////////// phase 2 END
    
  EXIT:;
    PRINT();
  }
  
  return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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 <bits/stdc++.h>

using namespace std;

int N;
int MX;
char output[500][500];

void PRINT() {
  for(int i=0; i<MX; i++) {
    cout << output[i] << endl;
  }
}

int main() {
  
  int Tc; cin >> Tc;
  bool blank = 0;
  while(Tc--) {
    if(blank) cout << endl;
    blank = 1;
    
    cin >> N;
    MX = N;
     
    for(int i=0; i<N; i++) {
      for(int j=0; j<N; j++) {
	output[i][j] = ' ';
      }
    }
    
    for(int i=0; i<N; i++) output[i][N] = 0;
    
    int cnt = 0;
    
    //////////////// phase 1 START
    
    int x = 0, y = N-1;
    for(int i=0; i<N; i++) {
      output[y-i][x] = '#';
    }
    y -= N-1;
    cnt ++;
    if(cnt == MX) goto EXIT;
        
    for(int i=0; i<N; i++) {
      output[y][x+i] = '#';
    }
    x += N-1;
    cnt ++;
    if(cnt == MX) goto EXIT;
    
    for(int i=0; i<N; i++) {
      output[y+i][x] = '#';
    }
    y += N-1;
    cnt ++;

    if(cnt == MX) goto EXIT;
    
    //////////////// phase 1 END
    
    
    //////////////// phase 2 START
    
    while(1) {
      
      N -= 2;
      for(int i=0; i<N; i++) {
	output[y][x-i] = '#';
      }
      
      x -= N-1;
      cnt ++;
      if(cnt == MX) goto EXIT;
      
      for(int i=0; i<N; i++) {
	output[y-i][x] = '#';
      }
      y -= N-1;
      cnt ++;
      if(cnt == MX) goto EXIT;
      
      N -= 2;
      
      for(int i=0; i<N; i++) {
	output[y][x+i] = '#';
      }
      x += N-1;
      cnt ++;
      if(cnt == MX) goto EXIT;
      
      for(int i=0; i<N; i++) {
	output[y+i][x] = '#';
      }
      y += N-1;
      cnt ++;
      if(cnt == MX) goto EXIT;
    }
    //////////////// phase 2 END
    
  EXIT:;
    PRINT();
  }
  
  return 0;
}
```