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;

//typedefs
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<long double, long double>pld;
typedef pair<double,double>pdd;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ld,ld>pld;
typedef pair<str,str>pss;
typedef pair<char,char>pcc;
typedef pair<long,long>pl;
typedef pair<bool,bool>pbb;

//defines
#define mp make_pair
#define pb push_back
#define pf push_front
#define PF pop_front
#define PB pop_back
#define P push
#define F first
#define fr front
#define bk back
#define S second
#define boost ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);srand(time(NULL))
#define PI 3.14159265
#define sz(s) (int)s.size()
#define sp(x) fixed << setprecision(x)
#define all(a) a.begin(),a.end()
#define mem(ar,a) memset(ar,a,sizeof(ar))
#define MT make_tuple
#define upper_bound ub
#define lower_bound lb
#define FOR(i,a,n,b) for (int i=a;i<n;i+=b)
#define rep(i,a,n) FOR (i,a,n,1)
#define ROF(i,a,n,b) for (int i=a;i>n;i-=b) 
#define vt vector
#define EACH(a,b) for (auto &a: b) 
#define mii map<int,int>
#define rtn return
#define gc getchar
#define pc putchar

//constants
const ll MOD = 1000000007LL;
const ll MOD2=998244353LL;
const ll high= 1LL<<50LL;
const int INF=1<<30;

//input

template <typename T> void read(T& num) {
	num=0;
	register int c;
	c=gc();
	bool isNeg=0;
	if (c=='-') c=gc(),isNeg=1;
	for (;(c>47&&c<58); c=gc()) num=num*10+c-48;
	if (isNeg) num*=-1;

}
void read(str &s) {
	s="";
	char c;
	while((c=gc())&&(c!=-1&&c!='\n'&&c!='\r'&&c!=' ')) s+=c;

}
void read(ld &num) {
	str s="";
	read(s);
	num=stold(s);
}
void read(double &num) {
	str s="";
	read(s);
	num=stod(s);
	
}
void read(char &a) {
	a=gc();
}

template<typename A, typename B> void read(pair<A,B> &a) {
	read(a.F);
	read(a.S);
}
template <typename G> void read(vt<G>&ar) {
	EACH(a,ar) 
		read(a);

}
template <typename H, typename... Types> void read(H&  num, Types&... num1) {
	read(num);
	read(num1...);
}

template<typename T=ll,typename M=ll, typename S=ll> ll modmul(T a, M b, S m) {ll ans=a*b-m*ll(1.L/m*a*b);return ans+m*(ans<0)-m*(ans>=m);}
template <typename T,typename S> ll Pow(T a, S b) {ll ret=1;while (b) {if (b&1) ret*=a;a*=a;b>>=1;}rtn ret;}
template <typename T=ll, typename S, typename M> T Pow(T a, S b, M mod) {T ans=1;for (; b;a=modmul(a,a,mod),b/=2) {if (b&1) ans=modmul(ans,a,mod);}rtn ans;}
template <typename A, typename B> A rando(A a, B b) { 
	return rand()%(b-a)+a;
}
int dx8[8]={1,1,-1,-1,2,2,-2,-2},dy8[8]={2,-2,2,-2,1,-1,1,-1},dx4[4]={1,-1,0,0},dy4[4]={0,0,1,-1}; 
clock_t start;
/*--------------------------------------------------------------PROGRAM START-------------------------------------------------------------------------*/

void solve(int n) {
	int ar[n][n],curr=1;
	mem(ar,-1);
	int stop;
	rep (i,0,n) {
		int x=i,y=0;
		while (x>=0&&y<n&&ar[x][y]==-1) {
		//	cout << x << " " << y << "\n";
			ar[x][y]=curr;
			++curr,--x,++y;
		}
		//cout << x << " " << y << "\n\n";
		int x1=n-1,y1=n-i-1;
		if (curr>n*n) break;
		while (x1>=0&&y1<n&&ar[x1][y1]==-1) {
			ar[x1][y1]=curr;
			x1--,y1++,curr++;
			//cout << x1 << " " << y1 << "\n";
		}
		//cout << "\n";
		
	}
	rep (i,0,n) {
		rep (j,0,n) {
			if (i) {
				if (abs(ar[i][j]-ar[i-1][j])==1) {
					cout << -1 << "\n";
					rtn;
				}
			}
			if (i+1<n) {
				if (abs(ar[i][j]-ar[i+1][j])==1) {
					cout << -1 << "\n";
					rtn;
				}
			}
			if (j) {
				if (abs(ar[i][j]-ar[i][j-1])==1) {
					cout << -1 << "\n";
					rtn;
				}
			}
			if (j+1<n) {
				if (abs(ar[i][j]-ar[i][j+1])==1) {
					cout << -1 << "\n";
					rtn;
				}
			}
		}
	}
	rep (i,0,n) {
		rep (j,0,n) {
			cout << ar[i][j];
			if (j+1<n) cout << " ";
			else cout << "\n";
		}
	}
	rtn;

}

int main() {
	boost;

	int t,n;
	read(t);
	while (t--) {
		read(n);
		solve(n);
	}

	rtn 0;
}