#include<iostream>
using namespace std;
#define MAX_D 101


bool dx[MAX_D][MAX_D];

void resetDx();
void makeDx();
void dispDx();
bool checkField(int n);
void make2();
int d;

int main(){
    int n;
    cin >>n;
    for(int i = 0; i < n; i++){
        if(i != 0) cout <<endl;
        resetDx();
        cin >>d;
        if(d == 2){
            make2();
        } else{
        makeDx();
        }
        /*for(int i = 0; i < d; i++){
            for(int j = 0; j < d; j++){
                cout <<dx[i][j];
            }
            cout <<endl;
        }*/
    }
    return 0;
}

void resetDx(){
    for(int i = 0; i < MAX_D; i++){
        for(int j = 0; j < MAX_D; j++){
            dx[i][j] = false;
        }
    }
}

void dispDx(){
    for(int i = 0; i < d; i++){
        for(int j = 0; j < d; j++){
            if(dx[i][j] == true) cout <<'#';
            else cout <<' ';
        }
        cout <<endl;
    }
}

void makeDx(){
    for(int i = 0; i < d; i++){
        dx[i][0] = true;
        dx[0][i] = true;
        dx[i][d - 1] = true;
    }
    int x = d - 1, y = d - 1, mx[4] = {-1, 0, 1, 0}, my[4] = {0, -1, 0, 1}, i = 0;
    bool moveFlg = false;
    while(true){
        while(checkField(x + mx[i]) && checkField(y + my[i]) && !dx[y + my[i] + my[i]][x + mx[i] + mx[i]]){
            if(!moveFlg) moveFlg = true;
            dx[y + my[i]][x + mx[i]] = true;
            x += mx[i]; y += my[i];
        }
        if(!moveFlg) break;
        //cout <<"now = " <<y <<", " <<x <<" iBefore = " <<i <<endl;
        i = (i + 1) % 4;
        int conti = (i + 2) % 4;
        int ny = y + my[i], nx = x + mx[i];
        bool endFlg = false;
        //cout <<"ny = " <<y <<"+" <<my[i] <<"=" <<ny <<", nx = " <<x <<"+" <<mx[i] <<"=" <<nx <<endl;
        for(int j = 0; j < 4; j++){
            if(j == conti) continue;
            else{
                if(checkField(ny + my[j]) && checkField(nx + mx[j])){
                    //cout <<"j = " <<j <<" ny + my[j] = " <<ny + my[j] <<", nx + mx[j] = " <<nx + mx[j];
                    if(dx[ny + my[j]][nx + mx[j]]){
                        //cout <<" true" <<endl;
                        endFlg = true;
                        break;
                    } else{
                        //cout <<" false" <<endl;
                    }
                }
            }
        }
        if(endFlg){
            break;
        }
        //dispDx();
    }
    dispDx();
}

bool checkField(int n){
    bool ret = true;
    if(n < 0 || n >= d) ret = false;
    return ret;
}

void make2(){
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            if(i == 1 && j == 1){
                dx[i][j] = false;
            } else{
                dx[i][j] = true;
            }
        }
    }
    dispDx();
}
### Prompt

Develop a solution in cpp 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;
#define MAX_D 101


bool dx[MAX_D][MAX_D];

void resetDx();
void makeDx();
void dispDx();
bool checkField(int n);
void make2();
int d;

int main(){
    int n;
    cin >>n;
    for(int i = 0; i < n; i++){
        if(i != 0) cout <<endl;
        resetDx();
        cin >>d;
        if(d == 2){
            make2();
        } else{
        makeDx();
        }
        /*for(int i = 0; i < d; i++){
            for(int j = 0; j < d; j++){
                cout <<dx[i][j];
            }
            cout <<endl;
        }*/
    }
    return 0;
}

void resetDx(){
    for(int i = 0; i < MAX_D; i++){
        for(int j = 0; j < MAX_D; j++){
            dx[i][j] = false;
        }
    }
}

void dispDx(){
    for(int i = 0; i < d; i++){
        for(int j = 0; j < d; j++){
            if(dx[i][j] == true) cout <<'#';
            else cout <<' ';
        }
        cout <<endl;
    }
}

void makeDx(){
    for(int i = 0; i < d; i++){
        dx[i][0] = true;
        dx[0][i] = true;
        dx[i][d - 1] = true;
    }
    int x = d - 1, y = d - 1, mx[4] = {-1, 0, 1, 0}, my[4] = {0, -1, 0, 1}, i = 0;
    bool moveFlg = false;
    while(true){
        while(checkField(x + mx[i]) && checkField(y + my[i]) && !dx[y + my[i] + my[i]][x + mx[i] + mx[i]]){
            if(!moveFlg) moveFlg = true;
            dx[y + my[i]][x + mx[i]] = true;
            x += mx[i]; y += my[i];
        }
        if(!moveFlg) break;
        //cout <<"now = " <<y <<", " <<x <<" iBefore = " <<i <<endl;
        i = (i + 1) % 4;
        int conti = (i + 2) % 4;
        int ny = y + my[i], nx = x + mx[i];
        bool endFlg = false;
        //cout <<"ny = " <<y <<"+" <<my[i] <<"=" <<ny <<", nx = " <<x <<"+" <<mx[i] <<"=" <<nx <<endl;
        for(int j = 0; j < 4; j++){
            if(j == conti) continue;
            else{
                if(checkField(ny + my[j]) && checkField(nx + mx[j])){
                    //cout <<"j = " <<j <<" ny + my[j] = " <<ny + my[j] <<", nx + mx[j] = " <<nx + mx[j];
                    if(dx[ny + my[j]][nx + mx[j]]){
                        //cout <<" true" <<endl;
                        endFlg = true;
                        break;
                    } else{
                        //cout <<" false" <<endl;
                    }
                }
            }
        }
        if(endFlg){
            break;
        }
        //dispDx();
    }
    dispDx();
}

bool checkField(int n){
    bool ret = true;
    if(n < 0 || n >= d) ret = false;
    return ret;
}

void make2(){
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            if(i == 1 && j == 1){
                dx[i][j] = false;
            } else{
                dx[i][j] = true;
            }
        }
    }
    dispDx();
}
```