The credit for us solving the problem in-contest goes to om_mittal7 who noticed that there was exactly $$$\frac{1}{2}$$$ chance that any given $$$n$$$ would have $$$(n-1,2)$$$ as a valid solution. Thereafter he tried extrapolating the idea to few more cases, and we ended up coding the following algorithm (without proof):

For $$$b_2$$$ in $$$2, 3, \cdots 1000$$$ let $$$[d_k,d_{k-1}, \cdots, d_1,d_0]_{b_2}$$$ be the base-$$$b_2$$$ representation of $$$n$$$. If there exists $$$b_1>b_2$$$ such that $$$d_k \cdot b_1+d_{k-1}=n$$$ and $$$d_k,d_{k-1}<b_1$$$, then $$$(b_1,b_2)$$$ is an answer. If nothing is found, print $$$-1$$$.

$$$1000$$$ was chosen as an arbitrarily high number that looked 'safe enough' (lol), Fortunately, the solution passed, leaving us relieved yet perplexed. However, when I tried later, I was completely stuck on how to prove its correctness.

It was only after I abandoned all previous ideas, and started from scratch with a completely new set of observations that I was able to chalk up the following proof, after which it became quite clear as to why this solution is correct. Sometimes a shift in perspective works wonders :-D

Fun fact: Brute forcing for values upto $$$10000$$$ revealed to me that $$${1,2,3,4,5,8,11,19}$$$ were the only inputs in that range for which the answer was $$$-1$$$. This suspiciously small bound turns up quite organically in the proof, which is one of the reasons why math is so beautiful (Spoiler: These are also the only inputs with answer $$$-1$$$).

/* 
 * author: twoplusthree 
 * created: 11.04.2024 20:24:53 
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
using vi=vector<int>;
void solve(){
  int n;
  cin>>n;
  if(n>=20){
    int b;
    int low,hig,mid;
    low=2;
    hig=1e9+5;
    while(low<=hig){
      mid=(low+hig)/2;
      if((mid+1)*mid<=n){
        b=mid;
        low=mid+1;
      }else{
        hig=mid-1;
      }
    }
    assert(2*b*b-1>=n);
    int q=n/b;
    int x=q-b; assert(1<=x&&x<=b-1);
    cout<<(n-x)<<" "<<b<<"\n";
  }else{
    auto tobase=[](int x,int b)->vi{
      vi res;
      while(x>0){
        res.push_back(x%b);
        x/=b;
      }
      reverse(all(res));
      return res;
    };
    vi bas[n];
    for(int i=2;i<n;i++){
      bas[i]=tobase(n,i);
    }
    auto isprefix=[](vi& v1,vi& v2)->bool{
      int n=(int)v1.size();
      if((int)v2.size()<n){
        return false;
      }
      for(int i=0;i<n;i++){
        if(v1[i]!=v2[i]){
          return false;
        }
      }
      return true;
    };
    for(int i=2;i<n;i++){
      for(int j=2;j<i;j++){
        if(isprefix(bas[i],bas[j])){
          cout<<i<<" "<<j<<"\n";
          return;
        }
      }
    }
    cout<<-1<<"\n";
  }
  return;
}
signed main(){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  int tt=1;
  cin>>tt;
  for(int i=1;i<=tt;i++){
    //cout<<"Case #"<<i<<": ";
    solve();
  }
  return 0;
}

Although we were unable to solve this problem in-contest, we had managed to make the pivotal claim about the case when $$$n$$$ is odd (albeit without proof).

One possible solution to the problems is where the answer for even $$$n$$$ is any Magic Square of order $$$\frac{n}{2}$$$, which can be constructed using a suitable construction algorithm (reference), which we unfortunately did not know at the time of the contest :(

However, a far simpler and arguably more elegant solution to the problem exists which was mainly inspired by the submission made by Team cns_lena_chahiye_tha (vikram108, ParadigmShift, dhruvsomani).

Clearly, $$$\max(R_i)\geq\frac{S}{r}$$$ and $$$\min(C_j)\leq\frac{S}{c}$$$ $$$\implies \max(R_i)-\min(C_j)\geq S\cdot\frac{c-r}{rc}$$$

From the problem statement, $$$S\cdot\frac{c-r}{rc} \leq \lceil\frac{n}{2}\rceil$$$

Since all the elements of $$$M$$$ are distinct, we can say $$$S\geq \displaystyle\sum_{i=0}^{rc-1}i=\frac{(rc-1)\cdot rc}{2}$$$.

Hence,

When $$$n=2m+1$$$,

$$$\frac{(2mr+r-r^2-1)(2m+1-2r)}{2} \leq m+1$$$

$$$\implies \frac{(2mr+r-r^2-1)(2m+1-2r)}{2} \leq m+1$$$

$$$\implies f(r)=2r^3-(6m+3)r^2+(4m^2+4m+3)r-(4m+3)\leq 0$$$

Studying the above function, we find that the curve first increases and then decreases in $$$0<r\leq \frac{2m+1}{2}$$$.

Putting $$$r=1$$$, we get $$$f(1)=4m^2-6m-1 >0 \ \forall m>1$$$

Putting $$$r=m$$$, we get $$$f(m)=m^2-m-3 >0 \ \forall m>2$$$

Hence, we can conclude that there does not exist any integral value of $$$r \in (0,\frac{n}{2}]$$$ such that the above condition is satisfied when $$$m>2$$$.

Let $$$(A_{i_1j_1},B_{i_1j_1})=(A_{i_2j_2},B_{i_2j_2})$$$.

Hence,

By $$$(2)-(1)$$$,

But,

/* 
 * author: twoplusthree 
 * created: 02.04.2024 01:30:38 
 */
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) (x).begin(),(x).end()
using vi=vector<int>;
void solve(){
  int n;
  cin>>n;
  if(n&1){
    if(n==3){
      cout<<"1 2\n";
      cout<<"0 1\n";
    }else if(n==5){
      cout<<"2 3\n";
      cout<<"0 3 4\n";
      cout<<"5 2 1\n";
    }else{
      cout<<-1<<"\n";
    }
  }else{
    int nn=n/2;
    vector<vi> A(nn,vi(nn));
    for(int i=0;i<nn;i++){
      for(int j=0;j<nn;j++){
        A[i][j]=(i+j)%nn;
      }
    }
    vector<vi> B(nn,vi(nn));
    for(int i=0;i<nn;i++){
      for(int j=0;j<nn;j++){
        B[i][j]=(2*i+j)%nn;
      }
    }
    vector<vi> ans(nn,vi(nn));
    for(int i=0;i<nn;i++){
      for(int j=0;j<nn;j++){
        ans[i][j]=nn*A[i][j]+B[i][j];
      }
    }
    cout<<nn<<" "<<nn<<"\n";
    for(int i=0;i<nn;i++){
      for(int j=0;j<nn;j++){
        cout<<ans[i][j]<<" ";
      }
      cout<<"\n";
    }
  }
  return;
}
signed main(){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  int tt=1;
  cin>>tt;
  for(int i=1;i<=tt;i++){
    //cout<<"Case #"<<i<<": ";
    solve();
  }
  return 0;
}