MAXSC

#include <iostream>
using namespace std;

int main() {
  long long int t,a[490000],sum,max,i,j,n,m,mi,secrow,min,f;
  cin>>t;
  while(t--)
  {
    cin>>n;
    for(i=(n*n)-1;i>=0;i--)
    {
      cin>>a[i];
    }

    f=0;
    m=n-1;
   
    mi=0;
    for(i=0;i<n;i++)
    {
      if(a[i]>mi)
      {
        mi=a[i];
      }
    }
    j=0;
    
    sum=mi;
    max = mi;
    j=n;
     
     while(m--)
    {   mi=0;
        for(i=0;i<n;i++)
          {
            if(a[i+j]>mi && a[i+j]<max)
            {
              
              mi=a[i+j];
              
            }
          }
          if(mi==0)
          {
            f=1;
            break;
          }
          max=mi;
          sum= sum + max;;
            j=j+n;
     }
     
     if(f==1)
     {
       cout<<-1<<endl;
     }
     else
     {
       cout<<sum<<endl;
     }
       
     
  }
  return 0;
}