#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define pb(a) push_back(a)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 30)
using namespace std;

void solve(char a[105][105], int inp, int d, int y, int x){
    int i;
    for(i = 0; i < inp - 1; i++){
        a[y][x] = '#';
        if(d == 0){
            if(a[y - 2][x] == '#') break;
            y--;
        }else if(d == 1){
            if(a[y][x + 2] == '#') break;
            x++;
        }else if(d == 2){
            if(a[y + 2][x] == '#') break;
            y++;
        }else{
            if(a[y][x - 2] == '#') break;
            x--;
        }
    }
    if(i <= 1) return;
    solve(a, inp, (d + 1) % 4, y, x);

}

int main(){
    int n;
    char a[105][105];
    cin >> n;
    rep(i,n){
        if(i) cout << endl;
        rep(i,105) rep(j,105) a[i][j] = ' ';
        int inp;
        cin >> inp;
        solve(a, inp, 0, 104, 0);
        if(inp == 1) cout << '#' << endl;
        else if(inp == 2) cout << "##" << endl << "# " << endl;
        else{
            for(int i = 104 - inp + 1; i <= 104; i++){
                rep(j,inp){
                    cout << a[i][j];
                }
                cout << endl;
            }
        }
    }
}
### Prompt

Your task is to create 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<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define pb(a) push_back(a)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 30)
using namespace std;

void solve(char a[105][105], int inp, int d, int y, int x){
    int i;
    for(i = 0; i < inp - 1; i++){
        a[y][x] = '#';
        if(d == 0){
            if(a[y - 2][x] == '#') break;
            y--;
        }else if(d == 1){
            if(a[y][x + 2] == '#') break;
            x++;
        }else if(d == 2){
            if(a[y + 2][x] == '#') break;
            y++;
        }else{
            if(a[y][x - 2] == '#') break;
            x--;
        }
    }
    if(i <= 1) return;
    solve(a, inp, (d + 1) % 4, y, x);

}

int main(){
    int n;
    char a[105][105];
    cin >> n;
    rep(i,n){
        if(i) cout << endl;
        rep(i,105) rep(j,105) a[i][j] = ' ';
        int inp;
        cin >> inp;
        solve(a, inp, 0, 104, 0);
        if(inp == 1) cout << '#' << endl;
        else if(inp == 2) cout << "##" << endl << "# " << endl;
        else{
            for(int i = 104 - inp + 1; i <= 104; i++){
                rep(j,inp){
                    cout << a[i][j];
                }
                cout << endl;
            }
        }
    }
}
```