Codeforces Round #719 (Div. 3) C. Not Adjacent Matrix Solution

C. Not Adjacent Matrix

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

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

• Each integer from 1$1$ to n2$n^2$ occurs in this matrix exactly once;
• If (r1,c1)$(r_1,c_1)$ and (r2,c2)$(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$t$ (1≤t≤100$1\le t\le 100$). Then t$t$ test cases follow.

Each test case is characterized by one integer n$n$ (1≤n≤100$1\le n\le 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$n$ lines, where each line contains n$n$ integers.

Example

input

Copy

3
1
2
3

output

Copy

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

 

#include <bits/stdc++.h>

using namespace std;

#define int            long long int

#define F              first

#define S              second

#define pb             push_back

#define si             set <int>

#define vi             vector <int>

#define pii            pair <int, int>

#define vpi            vector <pii>

#define vpp            vector <pair<int, pii>>

#define mii            map <int, int>

#define mpi            map <pii, int>

#define spi            set <pii>

#define endl           "\n"

#define sz(x)          ((int) x.size())

#define all(p)         p.begin(), p.end()

#define double         long double

#define que_max        priority_queue <int>

#define que_min        priority_queue <int, vi, greater<int>>

#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

#define print(a)       for(auto x : a) cout << x << " "; cout << endl

#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl

#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)

{

  int x = 1;

  while (b)

  {

    if (b & 1) x *= a;

    a *= a;

    b >>= 1;

  }

  return x;

}

template <typename Arg1>

void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f (const char* names, Arg1&& arg1, Args&&... args)

{

  const char* comma = strchr (names + 1, ',');

  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

}

const int N = 200005;

bool cmp(pair<int,int>a,pair<int,int>b){

    if((a.first+a.second)%2==0 && (b.first+b.second)%2==0){

        if(a.first!=b.first)return b.first>a.first;

        else return b.second>a.second;

    }

    if((a.first+a.second)%2!=0 && (b.first+b.second)%2!=0){

        if(a.first!=b.first)return b.first>a.first;

        else return b.second>a.second;

    }

    return (a.first+a.second)%2==0;

}

void solve() {

int n;

cin>>n;

if(n==1)cout<<1<<endl;

else if(n==2)cout<<-1<<endl;

else{

    vector<pair<int,int>>v;

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            v.pb({i,j});

        }

        

    }

    vector<vector<int>>ans(n,vector<int>(n,0));

    sort(v.begin(),v.end(),cmp);

    int k=1;

    for (int i = 0; i < n*n; i++)

    {

        ans[v[i].first][v[i].second]=k;

        k++;

        

    }

    for (int i = 0; i < n; i++)

    {

        print(ans[i]);

    }

    

}

}

int32_t main()

{

  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();

  int t = 1;

  cin >> t; 

  while (t--) solve();

  return 0;

}