#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
  
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) (s).rbegin(), (s).rend()
#define MP make_pair
#define X first
#define Y second
  
using namespace std;
  
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
 
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
 
void pp(vector<vi> &v){
    rep(i, v.size()){
        rep(j, v.size()){
            cout << v[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}
 
bool check(vector<vi> &v, int nx, int ny, int revdir){
    rep(i, 4){
        if(revdir == i) continue;
        int x = nx+dx[i];
        int y = ny+dy[i];
        if(v[y][x] == 1) return false;
    }
    return true;
}
 
int main(){
    int d;
    cin >> d;
    rep(k, d){
        if(k)cout << endl;
        int n;
        cin >> n;
        vector<vi> v(n+4, vi(n+4, 0));
        rep(i, n+4) rep(j, n+4) if(i == 0 || i == n+3 || j == 0 || j == n+3) v[i][j] = 1;
        int x = 2;
        int y = n+3-2;
        int dir = 0;
        v[y][x] = 1;
 
        bool end = false;
        while(1){
            int nx = x+dx[dir];
            int ny = y+dy[dir];
            if(check(v, nx, ny, (dir+2)%4)){
                v[ny][nx] = 1;
                x = nx, y = ny;
                end = false;
            }else{
                dir = (dir+1)%4;
                if(end) break;
                end = true;
            }
        }
 
        //pp(v);
        for(int i = 2; i < n+2; i++){
            for(int j = 2; j < n+2; j++){
                cout << (v[i][j]?'#':' ');
            }
            cout << endl;
        }
    }
 
    return 0;
}
### 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 <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
  
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) (s).rbegin(), (s).rend()
#define MP make_pair
#define X first
#define Y second
  
using namespace std;
  
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
 
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
 
void pp(vector<vi> &v){
    rep(i, v.size()){
        rep(j, v.size()){
            cout << v[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}
 
bool check(vector<vi> &v, int nx, int ny, int revdir){
    rep(i, 4){
        if(revdir == i) continue;
        int x = nx+dx[i];
        int y = ny+dy[i];
        if(v[y][x] == 1) return false;
    }
    return true;
}
 
int main(){
    int d;
    cin >> d;
    rep(k, d){
        if(k)cout << endl;
        int n;
        cin >> n;
        vector<vi> v(n+4, vi(n+4, 0));
        rep(i, n+4) rep(j, n+4) if(i == 0 || i == n+3 || j == 0 || j == n+3) v[i][j] = 1;
        int x = 2;
        int y = n+3-2;
        int dir = 0;
        v[y][x] = 1;
 
        bool end = false;
        while(1){
            int nx = x+dx[dir];
            int ny = y+dy[dir];
            if(check(v, nx, ny, (dir+2)%4)){
                v[ny][nx] = 1;
                x = nx, y = ny;
                end = false;
            }else{
                dir = (dir+1)%4;
                if(end) break;
                end = true;
            }
        }
 
        //pp(v);
        for(int i = 2; i < n+2; i++){
            for(int j = 2; j < n+2; j++){
                cout << (v[i][j]?'#':' ');
            }
            cout << endl;
        }
    }
 
    return 0;
}
```