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;
#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3")
#define F first
#define S second
#define sz size()
#define pb push_back
#define int long long
#define all(x) (x).begin(),(x).end()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
template <class T> inline T pw(T a, int n,  T res = 1){while (n) {if (n & 1) res *= a;a *= a;n >>= 1;}return res;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
const int E = 1e6+777;
const int inf = 1e18+777;
const int N = 1e5+777;
const int dx[] = {0, 1, -1, 0, 0, 0};
const int dy[] = {0, 0, 0, -1, 1, 0};
signed main(){auto solve=[&](){
	int n ;
	cin >> n;
	if(n == 2){
		cout << "-1\n";
		return;
	}
	vector<vector<int>>mt(n+2,vector<int>(n+2,0));
	vector<pair<int,int> >v = {{1,1}};
	for(int i = 2; i <= n; i++){
		v.pb({1,i});
		v.pb({i,1});
	}	
	int cur = 1;
	for(auto i : v){
		for(int j = 0; j <= n; j++){
			int x = i.F + j , y = i.S + j;
			if(x <= n && x >= 1 && y <= n && y >= 1){
				mt[x][y] = cur++;
			}
		}	
	}cout << '\n';
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cout << mt[i][j] << " \n"[j==n];
};NFS;int T;cin>>T;while(T--)solve();}