#include<iostream>
using namespace std;

int main()
{
    int n, d;

    cin >> n;

    for( int i = 0; i < n; i++ )
    {
        cin >> d;

        if( i >= 1 )
            cout << endl;

        if( d == 1 )
        {
            cout << "#" << endl;
            continue;
        }
        else if( d == 2 )
        {
            cout << "##" << endl;
            cout << "# " << endl;
            continue;
        }

        char a[d][d], cnt = 3;
        for( int j = 0; j < d; j++ )
            for( int k = 0; k < d; k++ )
                a[j][k] = ' ';

        for( int j = 0; j < d; j++ )
        {
            a[j][0] = '#';
            a[0][j] = '#';
            a[j][d-1] = '#';
        }

        int x = d - 1, y = d - 1;
        while( 1 )
        {
            if( cnt != d )
            {
                while( a[x][y-2] != '#' )
                {
                    a[x][y-1] = '#';
                    y--;
                }
                cnt++;
            }
            else
                break;

            if( cnt != d )
            {
                while( a[x-2][y] != '#' )
                {
                    a[x-1][y] = '#';
                    x--;
                }
                cnt++;
            }
            else
                break;

            if( cnt != d )
            {
                while( a[x][y+2] != '#' )
                {
                    a[x][y+1] = '#';
                    y++;
                }
                cnt++;
            }
            else
                break;

            if( cnt != d )
            {
                while( a[x+2][y] != '#' )
                {
                    a[x+1][y] = '#';
                    x++;
                }
                cnt++;
            }
            else
                break;            
        }
        for( int j = 0; j < d; j++ )
        {
            for( int k = 0; k < d; k++ )
                cout << a[j][k];
            cout << endl;
        }
    }
    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<iostream>
using namespace std;

int main()
{
    int n, d;

    cin >> n;

    for( int i = 0; i < n; i++ )
    {
        cin >> d;

        if( i >= 1 )
            cout << endl;

        if( d == 1 )
        {
            cout << "#" << endl;
            continue;
        }
        else if( d == 2 )
        {
            cout << "##" << endl;
            cout << "# " << endl;
            continue;
        }

        char a[d][d], cnt = 3;
        for( int j = 0; j < d; j++ )
            for( int k = 0; k < d; k++ )
                a[j][k] = ' ';

        for( int j = 0; j < d; j++ )
        {
            a[j][0] = '#';
            a[0][j] = '#';
            a[j][d-1] = '#';
        }

        int x = d - 1, y = d - 1;
        while( 1 )
        {
            if( cnt != d )
            {
                while( a[x][y-2] != '#' )
                {
                    a[x][y-1] = '#';
                    y--;
                }
                cnt++;
            }
            else
                break;

            if( cnt != d )
            {
                while( a[x-2][y] != '#' )
                {
                    a[x-1][y] = '#';
                    x--;
                }
                cnt++;
            }
            else
                break;

            if( cnt != d )
            {
                while( a[x][y+2] != '#' )
                {
                    a[x][y+1] = '#';
                    y++;
                }
                cnt++;
            }
            else
                break;

            if( cnt != d )
            {
                while( a[x+2][y] != '#' )
                {
                    a[x+1][y] = '#';
                    x++;
                }
                cnt++;
            }
            else
                break;            
        }
        for( int j = 0; j < d; j++ )
        {
            for( int k = 0; k < d; k++ )
                cout << a[j][k];
            cout << endl;
        }
    }
    return 0;
}

```