Problem: We will consider the numbers a and b as adjacent if they differ by exactly one, that is, |a-b|=1.

We will consider cells of a square matrix n × n as adjacent if they have a common side, that is, for cell (r, c) cells (r, c-1), (r, c+1), (r-1, c) and (r+1, c) are adjacent to it.

For a given number n, construct a square matrix n × n such that: 

  * Each integer from 1 to n^2 occurs in this matrix exactly once; 
  * If (r_1, c_1) and (r_2, c_2) are adjacent cells, then the numbers written in them must not be adjacent. 

Input

The first line contains one integer t (1 ≤ t ≤ 100). Then t test cases follow.

Each test case is characterized by one integer n (1 ≤ n ≤ 100).

Output

For each test case, output: 

  * -1, if the required matrix does not exist; 
  * the required matrix, otherwise (any such matrix if many of them exist). 



The matrix should be outputted as n lines, where each line contains n integers.

Example

Input


3
1
2
3


Output


1
-1
2 9 7
4 6 3
1 8 5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define ull unsigned long long

#define pii pair<int, int>
#define pll pair<ll,ll>
#define pld pair<ld, ld>
#define vll vector<ll>
#define vld vector<ld>
#define vii vector<int>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vpii vector<pii>
#define vpll vector<pll>
#define vpld vector<pld>
#define sii set<int>
#define sll set<ll>
#define sld set<ld>
#define sc set<char>
#define ss set<string>

#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()

#define debug(a) cout << a << endl;
#define debug2(a, b) cout << a <<  ' ' << b << endl;
#define debug3(a, b, c) cout << a << ' ' << b << ' ' << c << endl;
#define debug4(a, b, c, d) cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
#define debug5(a, b, c, d, e) cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << endl;

#define f(a, b, c) for (auto a = b; a < c; a++)
#define fe(a, b, c) for (auto a = b; a <= c; a++)
#define fr(a, b, c) for (auto a = b; a >= c; a--)

#define cinvec(v) f(i, 0, v.size()) cin >> v[i]
#define coutvec(v) for (auto i : v) cout << i << " "; cout << endl;

#define pb push_back

#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int MAX_INT = INT32_MAX;
const ll MAX_LL = INT64_MAX;
const ll mod = 1e9 + 7;
const int N = 1;
const ld pi = 3.14159265359;
bool primes[N + 1];

void sieve()
{
    memset(primes, true, sizeof(primes));
    primes[0] = primes[1] = false;
    for (int i = 2; i * i <= N; i++){
        if (primes[i]){
            for (int j = i * i; j <= N; j += i) primes[j] = false;
        }
    }
}

void moveOneStep(ll& n, ll& d, ll q)
{
    ll next = n - d * q;
    n = d;
    d = next;
}

bool isPrime(ll n)
{
    if (n <= 1) return false;
    if (n == 2) return true;
    fe (i, 2, sqrt(n)) if (n % i == 0) return false;
    return true;
}

bool palindrome(const string& s)
{
    string reversedS = s;
    reverse(all(reversedS));
    if (s == reversedS) return true;
    else return false;
}

ll gcd(ll a, ll b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}

ll eGCD(ll r0, ll r1, ll& x0, ll& y0)
{
    ll x1, y1;
    x0 = y1 = 1;
    x1 = y0 = 0;
    while (r1) {
        ll q = r0 / r1;
        moveOneStep(x0, x1, q);
        moveOneStep(y0, y1, q);
        moveOneStep(r0, r1, q);
    }
    return r0;
}

ll modInv(ll c, ll M)
{
    ll x, y;
    ll g = eGCD(c, M, x, y);
    if (g != 1) return -1;
    return x;
}

ll npr(ll n, ll r)
{
    ll res = 1; fe (i, n - r + 1, n) res *= i;
    return res;
}

ll ncr(ll n, ll r)
{
    ll res = 1; ll rFact = 1;
    fe (i, n - r + 1, n){
        res *= i;
        if (res % rFact == 0 && rFact <= r) res /= rFact, rFact++;
    }
    return res;
}

ll fastPow(ll base, ll power)
{
    if (power == 1) return base;
    ll val = fastPow(base, power / 2);
    return (power % 2 == 0) ? val * val : val * val * base;
}

ll modPow(ll base, ll power, ll M)
{
    if (power == 1) return base;
    ll val = modPow(base, power / 2, M);
    return (power % 2 == 0) ? (val * val) % M : (((val * val) % M) * base) % M;
}

sll getDivisors(ll val)
{
    sll st;
    fe (i, 1, sqrt(val)) if (val % i == 0) st.insert(i), st.insert(val / i);
    return st;
}

int main() {
    FastIO
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int arr[n][n];
        ll e = 2, o = 1;
        bool valid = true;
        f(i, 0, n) {
            f(j, 0, n) {
                if (e <= n * n) arr[j][i] = e, e += 2;
                else arr[j][i] = o, o += 2;
                if (i > 0) {
                    if (abs(arr[j][i] - arr[j][i - 1]) == 1) valid = false;
                }
                if (j > 0) {
                    if (abs(arr[j][i] - arr[j - 1][i]) == 1) valid = false;
                }
            }
        }
        if (!valid) {
            cout << -1 << endl;
            continue;
        }
        f(i, 0, n) {
            f(j, 0, n) cout << arr[i][j] << ' ';
            cout << endl;
        }
    }
    return 0;
}