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>
using namespace std;
/**
   ********************************************************************
   * EEEEE     EEEEEE         E        EEEEEEE   EEEEEEE    E       E *
   * E    E    E     E       E E       E     E   E     E    E E     E *
   * E     E   E    E       E   E      E         E     E    E  E    E *
   * E      E  EEEEE       E     E     E   EEE   E     E    E   E   E *
   * E     E   EEE        EEEEEEEEE    E     E   E     E    E    E  E *
   * E    E    E  E      E         E   E     E   E     E    E     E E *
   * EEEEE     E    E   E           E  EEEEEEE   EEEEEEE    E       E *
   ********************************************************************
*/

#define endl          '\n'
#define all(v)        v.begin(),v.end()
#define rep(i,t,n)    for(int i = t ; i < n ; i++)
#define fast          ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define readFromText  readF()
#define deb(...)      __f(#__VA_ARGS__, __VA_ARGS__)
#define repeat(x)     while(x--)
#define MOD           1000000007

template <typename Arg1>void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 <<'\n';}template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1 << " | ";__f(comma + 1, args...);}
typedef long long ll;
typedef vector<ll> vll;
typedef map<string,ll> slmp;
typedef map<ll,ll> llmp;
typedef pair<ll,ll> pll;

long long gcdd (long long a , long long b) {
    if (b==0)return a;
    return gcdd(b,a%b);
}

double lcmm (double a , double b) {
    return (a*gcdd(a,b))/b*1.0;
}


void readF (){
    #ifndef ONLINE_JUDGE
freopen("C:/Users/Anas-Hagras/Desktop/input.txt","r",stdin);
    #endif // ONLINE_JUDGE
}

bool compare (char a, char b){
    return a >= b ;
}

string bin (ll x){
    x = abs(x);
    string ans = "";
    for (int i = 0 ; i <= 62 ; i++)ans+="0";
    int i = ans.length()-1;
    while(x>0){
        if(x%2!=0)ans[i]='1';
        else ans[i]='0';
        i--,x/=2;
    }
    return ans ;
}

string actBin (ll x) {
    string ans = bin(x);
    for (int i = 0 ; i < ans.length() ; i++){
        if (ans[i]=='1')return ans.substr(i);
    }
    return ans;
}

bool isPower2 (ll x){
    return x && !(x & (x-1));
}

ll getCloser (long long x){
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    x |= (x >> 32);
    return (x+1)>>1;
}

ll getLastOne (long long x){
    return x ^ ( x & (x-1));
}

double getDis (double a, double b , double c , double d) {
    return sqrt(pow(c-a,2)+pow(d-b,2));
}

pair<double,double> getMiddle (double a, double b , double c , double d){
    return {(a+c)/2,(d+b)/2};
}

// bitset
// builtin_popcount(n) >> counter ones
// x| x+1 >> first one to zero
// x& x-1 >> first zero to one
// x& x+1 >> first ones to zeros
// x| x-1 >> first zeros to ones

string act(string ans);

string act (string ans) {
    for (int i = 0 ; i < ans.length() ; i++){
        if (ans[i]!='0')return ans.substr(i);
    }
    return ans;
}

long double fact (ll x){
    long double a = 1;
    for (int i = x ; i >= 1 ; i--){
        a*=i;
    }
    return a;
}

string bits(ll n) {
    deb(n);
    if (n==0)return "";
    return bits(n/2)+to_string(n%2);
}

bool pali (string s){
    string ss = s;
    reverse(all(ss));
    return s == ss;
}

//const int M = 500;
//int grid [M][M];
ll n , m , k , l , r ,d ;
const int MX = 2e6;
ll a[MX+5],b[MX];
string s1,s2;
vector<ll>v1,v2;
const int FMX = 1e6;
ll f[FMX+9];
void fib(){
    f[0] = 1;
    f[1] = 1;
    for(ll i = 2 ; i <= FMX ; i++){
       f[i] = (f[i-1]%MOD + f[i-2]%MOD)%MOD;
    }
}

ll sumOfEven (ll x){
    return (x/2)*((x/2)+1);
}

ll sumOfOdd(ll x){
    return (x*(x+1)/2) - sumOfEven(x);
}

ll sumToN(ll x){
    return (x*(x+1)/2);
}

ll getDiv(ll x){
    return x/k;
}

ll getFirst(){
    if (n%k==0)return n;
    return k*((n/k)+1);
}

bool isEqual(double x, double y, double epsilon = 0.0000001f){
   if(fabs(x - y) < epsilon)
      return true;
      return false;
}

ll npr(ll x , ll r)
{
    if(r>x)return 0;
    ll an = 1;
    rep(i,x-r+1,x+1)an*=i;
    return an;
}
ll ncr(ll x,ll r)
{
    if(r>x)return 0;
    return npr(x,r)/fact(r);
}

int main (){
    fast;
    readF();
    int t = 1;
    cin >> t;
    repeat(t){
        cin >> n;
        if (n==2){
            cout << -1 << endl;
            continue;
        }else {
            int firstStart = 1;
            int secondStart = 2;
            int tt = 1;
            for (int i = 1 ; firstStart <= (n*n) ; i++){
                cout << firstStart << " ";
                firstStart+=2;
                if (tt==n)cout << endl,tt=0;
                tt++;
            }
            for (int i = 1 ; secondStart<=(n*n); i++){
                cout << secondStart << " ";
                secondStart+=2;
                if (tt==n)cout << endl,tt=0;
                tt++;
            }
        }
    }
    return 0;
}