#include <iostream>
#include <cstdlib>
const static int SIZE = 100;
const static int MARGIN = 2;

const static int F_NONE = 0;
const static int F_WALL = 1;
const static int F_LINE = 2;

const static int DIR_N = 4;

using namespace std;


void draw( int n ) {
  int field[ SIZE + MARGIN * 2 ][ SIZE + MARGIN * 2 ] = { 0 };
  int pos_y = n + MARGIN - 1;
  int pos_x = MARGIN;
  int vy[] = { -1, 0, 1,  0 };
  int vx[] = {  0, 1, 0, -1 };
  int dir = 0;
  int lastMoveDir = -1;
  int turnNum = 0;
  for( int i = 0; i < n + MARGIN * 2; i++ ) {
    field[ i ][ 0 ] = F_WALL;
    field[ 0 ][ i ] = F_WALL;
    field[ i ][ n + MARGIN * 2 - 1 ] = F_WALL;
    field[ n + MARGIN * 2 - 1 ][ i ] = F_WALL;
  }

  while( 1 ) {
    field[ pos_y ][ pos_x ] = F_LINE;
    if(
      field[ pos_y + vy[ dir ] * 2 ][ pos_x + vx[ dir ] * 2 ] == F_NONE 
    ) {
      pos_y += vy[ dir ];
      pos_x += vx[ dir ];
      lastMoveDir = dir;
    } else {
      dir = ( dir + 1 ) % DIR_N;
      if( turnNum++ == n - 1 ) { break; }
    }
  }

  for( int i = MARGIN; i < n + MARGIN; i++ ) {
    for( int j = MARGIN; j < n + MARGIN; j++ ) {
      cout << ( field[ i ][ j ] ? '#' : ' ' ) << flush;
    }
    cout << endl;
  }
}


int main() {
  int d;
  cin >> d;
  for( int i = 0; i < d; i++ ) {
    int n;
    cin >> n;
    draw( n );
    if( i != d - 1 ) {
      cout << endl;
    }
  }
  return EXIT_SUCCESS;
}
### Prompt

Please formulate 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>
#include <cstdlib>
const static int SIZE = 100;
const static int MARGIN = 2;

const static int F_NONE = 0;
const static int F_WALL = 1;
const static int F_LINE = 2;

const static int DIR_N = 4;

using namespace std;


void draw( int n ) {
  int field[ SIZE + MARGIN * 2 ][ SIZE + MARGIN * 2 ] = { 0 };
  int pos_y = n + MARGIN - 1;
  int pos_x = MARGIN;
  int vy[] = { -1, 0, 1,  0 };
  int vx[] = {  0, 1, 0, -1 };
  int dir = 0;
  int lastMoveDir = -1;
  int turnNum = 0;
  for( int i = 0; i < n + MARGIN * 2; i++ ) {
    field[ i ][ 0 ] = F_WALL;
    field[ 0 ][ i ] = F_WALL;
    field[ i ][ n + MARGIN * 2 - 1 ] = F_WALL;
    field[ n + MARGIN * 2 - 1 ][ i ] = F_WALL;
  }

  while( 1 ) {
    field[ pos_y ][ pos_x ] = F_LINE;
    if(
      field[ pos_y + vy[ dir ] * 2 ][ pos_x + vx[ dir ] * 2 ] == F_NONE 
    ) {
      pos_y += vy[ dir ];
      pos_x += vx[ dir ];
      lastMoveDir = dir;
    } else {
      dir = ( dir + 1 ) % DIR_N;
      if( turnNum++ == n - 1 ) { break; }
    }
  }

  for( int i = MARGIN; i < n + MARGIN; i++ ) {
    for( int j = MARGIN; j < n + MARGIN; j++ ) {
      cout << ( field[ i ][ j ] ? '#' : ' ' ) << flush;
    }
    cout << endl;
  }
}


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