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;

#define time  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define lli long long
//#define int long long 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define fo(i,n) for(i=0;i<n;i++)
#define ffo(i,a,n) for(i=a;i<n;i++)
#define PI 3.1415926535897932384626
#define mod             1000000007
#define inf             1e18
#define dlli long double
const lli MAX=1e9+7;
//const ll Large=2e5+5;
//int p=k-'0'; char to int ;
typedef pair<int, int>	pii;
//typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<vi>		vvi;
typedef map<int,int>	mii;
//<==============================================>
int cal(int j){	
	int sum1=((j)*(j-1))/2;
	return(sum1);
}
lli gcd(lli a, lli b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
  
// Function to find gcd of array of 
// numbers 
int findGCD(int arr[], int n) 
{ 
    int result = arr[0]; 
    for (int i = 1; i < n; i++) 
    { 
        result = gcd(arr[i], result); 
  
        if(result == 1) 
        { 
           return 1; 
        } 
    } 
    return result; 
} 
int lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
 
bool isPrime(int n) 
{ 
    // Corner case 
    if (n <= 1) 
        return false; 
  
    // Check from 2 to n-1 
    for (int i = 2; i < n; i++) 
        if (n % i == 0) 
            return false; 
  
    return true; 
} 
lli power(lli x, lli y, lli p) 
{ 
    lli res = 1; // Initialize result 
    x = x % p; // Update x if it is more than or 
    // equal to p 
    while (y > 0) { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res * x) % p; 
  
        // y must be even now 
        y = y >> 1; // y = y/2 
        x = (x * x) % p; 
    } 
    return res; 
} 
bool isNumber(string s)
{
    for (int i = 0; i < s.length(); i++)
        if (isdigit(s[i]) == false)
            return false;
 
    return true;
}
int maxi(int a,int b,int c){
	int ma=max(a,b);
	return(max(ma,c));
}
int ldn(int n){
	if(n%2==0) return(2);
	else{
		int i;
		for(i=3;i*i<=n;i++){
			if(n%i==0) return(i);	
		}
		return(n);
	}
}

lli dig(lli n){
	lli sum=0;
	while(n>0){
		sum++; n=n/10;
	}
	return(sum);
}

bool is_integer(float k)
{
  return std::floor(k) == k;
}
bool isy(long double x)
{
    // Find floating point value of
    // square root of x.
    if (x >= 0) {
 
        long long sr = sqrt(x);
         
        // if product of square root
        //is equal, then
        // return T/F
        return (sr * sr == x);
    }
    // else return false if n<0
    return false;
}
int cross(lli n){
	
}

void mycode() {
	
	lli n=0,li,ri,i,x,j=-1,d=0,k=0,m=0,count=0,sum=0;
	string s="",s1;
	cin>>n;
	lli tab[n][n];
	i=1;
	j=0;k=0;
	while(i<=n*n){
		if(k==n){
			j++;
			k=0;
		}
		tab[j][k]=i;
		k++;
		i+=2;
	}
	i=2;
	while(i<=n*n){
		if(k==n){
			j++;
			k=0;
		}
		tab[j][k]=i;
		k++;
		i+=2;
	}
	if(n==2) cout<<-1<<endl;
	else{
		for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			cout<<tab[i][j]<<" ";
		}
		cout<<endl;
	}
	}
//	cout<<endl;
}


int32_t main()
{
    time;
	//    freopen("input.txt", "r", stdin);
	//    freopen("output.txt", "w", stdout);  
    int t = 1;
    cin >> t;
//	t=50;
    while(t--) {
      mycode();
    }
    return 0;
}