// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int n) { return n & 1; }
constexpr bool even(const int n) { return ~n & 1; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

main {
  int d;
  cin >> d;
  while (d--) {
    int n;
    cin >> n;
    vs v(n, string(n, ' '));
    vi di = {-1, 0, 1, 0}, dj = {0, 1, 0, -1};
    auto canPut = [&](int i, int j) {
      if (i < 0 || j < 0 || i >= n || j >= n) return false;
      int c = 0;
      c += i - 1 >= 0 && v[i - 1][j] == '#';
      c += j - 1 >= 0 && v[i][j - 1] == '#';
      c += i + 1 < n && v[i + 1][j] == '#';
      c += j + 1 < n && v[i][j + 1] == '#';
      return c <= 1;
    };
    int i = n, j = 0, t = 0;
    forever {
      int ni = i + di[t], nj = j + dj[t];
      if (canPut(ni, nj)) {
        i = ni;
        j = nj;
        v[i][j] = '#';
        continue;
      }
      t = (t + 1) % 4;
      ni = i + di[t], nj = j + dj[t];
      if (canPut(ni, nj)) {
        i = ni;
        j = nj;
        v[i][j] = '#';
        continue;
      }
      break;
    }
    for (auto &x : v) cout << x << endl;
    if (d) cout << endl;
  }
}
### 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
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int n) { return n & 1; }
constexpr bool even(const int n) { return ~n & 1; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

main {
  int d;
  cin >> d;
  while (d--) {
    int n;
    cin >> n;
    vs v(n, string(n, ' '));
    vi di = {-1, 0, 1, 0}, dj = {0, 1, 0, -1};
    auto canPut = [&](int i, int j) {
      if (i < 0 || j < 0 || i >= n || j >= n) return false;
      int c = 0;
      c += i - 1 >= 0 && v[i - 1][j] == '#';
      c += j - 1 >= 0 && v[i][j - 1] == '#';
      c += i + 1 < n && v[i + 1][j] == '#';
      c += j + 1 < n && v[i][j + 1] == '#';
      return c <= 1;
    };
    int i = n, j = 0, t = 0;
    forever {
      int ni = i + di[t], nj = j + dj[t];
      if (canPut(ni, nj)) {
        i = ni;
        j = nj;
        v[i][j] = '#';
        continue;
      }
      t = (t + 1) % 4;
      ni = i + di[t], nj = j + dj[t];
      if (canPut(ni, nj)) {
        i = ni;
        j = nj;
        v[i][j] = '#';
        continue;
      }
      break;
    }
    for (auto &x : v) cout << x << endl;
    if (d) cout << endl;
  }
}
```