#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;
typedef vector<string> VS;
typedef int INT;
typedef vector<INT> VI;
typedef vector<VI> VVI;
typedef pair <INT, INT> II;
typedef vector <II> VII;

template<class T> ostream& operator << ( ostream& os, vector<T> v ) {
    for ( typename vector<T>::iterator it_i = v.begin(); it_i != v.end(); ++it_i ) {
        os << *it_i << ", ";
    }
    return os;
}


void solve( int d ) {
    bool T[d][d];
    int r = d - 1, c = 0;
    const int dr[4] = { -1, 0, 1, 0 };
    const int dc[4] = { 0, 1, 0, -1 };
    int k = 0;
    fill( (bool*)T, (bool*)T+d*d, false );

    for ( int lpc = 0; lpc < d * d; ++ lpc ) {
        T[r][c] = true;
        bool flag = false;
        for ( int i = 0; i < 2; ++ i ) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if ( nr < 0 || nr >= d || nc < 0 || nc >= d ) {
                k = ( k + 1 ) % 4;
                continue;
            }
            int nnr = r + dr[k] * 2;
            int nnc = c + dc[k] * 2;
            if ( nnr < 0 || nnr >= d || nnc < 0 || nnc >= d ) {
                r = nr;
                c = nc;
                flag = true;
                break;
            }
            if ( T[nnr][nnc] ) {
                k = ( k + 1 ) % 4;
                continue;
            }
            r = nr;
            c = nc;
            flag = true;
            break;
        }
        int cnt = 0;
        for ( int i = 0; i < 4; ++ i ) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if ( nr < 0 || nr >= d || nc < 0 || nc >= d ) continue;
            if ( T[nr][nc] ) cnt ++;
        }
        if ( cnt > 1 ) break;
    }

    for ( int i = 0; i < d; ++ i ) {
        for ( int j = 0; j < d; ++ j ) {
            cout << ( T[i][j] ? '#' : ' ' );
        }
        cout << endl;
    }
}

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

Generate 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 <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;
typedef vector<string> VS;
typedef int INT;
typedef vector<INT> VI;
typedef vector<VI> VVI;
typedef pair <INT, INT> II;
typedef vector <II> VII;

template<class T> ostream& operator << ( ostream& os, vector<T> v ) {
    for ( typename vector<T>::iterator it_i = v.begin(); it_i != v.end(); ++it_i ) {
        os << *it_i << ", ";
    }
    return os;
}


void solve( int d ) {
    bool T[d][d];
    int r = d - 1, c = 0;
    const int dr[4] = { -1, 0, 1, 0 };
    const int dc[4] = { 0, 1, 0, -1 };
    int k = 0;
    fill( (bool*)T, (bool*)T+d*d, false );

    for ( int lpc = 0; lpc < d * d; ++ lpc ) {
        T[r][c] = true;
        bool flag = false;
        for ( int i = 0; i < 2; ++ i ) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if ( nr < 0 || nr >= d || nc < 0 || nc >= d ) {
                k = ( k + 1 ) % 4;
                continue;
            }
            int nnr = r + dr[k] * 2;
            int nnc = c + dc[k] * 2;
            if ( nnr < 0 || nnr >= d || nnc < 0 || nnc >= d ) {
                r = nr;
                c = nc;
                flag = true;
                break;
            }
            if ( T[nnr][nnc] ) {
                k = ( k + 1 ) % 4;
                continue;
            }
            r = nr;
            c = nc;
            flag = true;
            break;
        }
        int cnt = 0;
        for ( int i = 0; i < 4; ++ i ) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if ( nr < 0 || nr >= d || nc < 0 || nc >= d ) continue;
            if ( T[nr][nc] ) cnt ++;
        }
        if ( cnt > 1 ) break;
    }

    for ( int i = 0; i < d; ++ i ) {
        for ( int j = 0; j < d; ++ j ) {
            cout << ( T[i][j] ? '#' : ' ' );
        }
        cout << endl;
    }
}

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