#include <bits/stdc++.h>
using namespace std;

// #include <atcoder/all>
// using namespace atcoder;

#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;


void solve(long long N, long long K, std::vector<std::vector<long long>> A){
    // 中央値を ll 以下にすることが可能か
    int ok = 1e9;
    int ng = -1;
    auto check = [&](int l) {
        vector<vector<int>> cum1(N, vector<int>(N + 1));
        rep(i, N) {
            rep(j, N) {
                cum1[i][j + 1] = cum1[i][j] + (A[i][j] <= l);
            }
        }
        vector<vector<int>> cum2(N + 1, vector<int>(N + 1));
        rep(i, N) {
            rep(j, N + 1) {
                cum2[i + 1][j] = cum2[i][j] + cum1[i][j];
            }
        }
        // printf("l: %ld\n", l);
        rep(i, N + 1) {
            rep(j, N + 1) {
                // printf("%ld ", cum2[i][j]);
            }
            // printf("\n");
        }
        rep(i, N - K + 1) {
            rep(j, N - K + 1) {
                if (
                    cum2[i + K][j + K]
                    - cum2[i + K][j]
                    - cum2[i][j + K]
                    + cum2[i][j] >= (K * K + 1) / 2) {
                    // printf("OK\n");
                    return 1;
                }
            }
        }

        // printf("NG\n");
        return 0;
    };
    while (ok - ng > 1) {
        int l = (ok + ng) / 2;
        (check(l) ? ok : ng) = l;
    }
    cout << ok << endl;
}

// Generated by 2.3.1 https://github.com/kyuridenamida/atcoder-tools
int main(){
    long long N;
    std::scanf("%lld", &N);
    long long K;
    std::scanf("%lld", &K);
    std::vector<std::vector<long long>> A(N, std::vector<long long>(N));
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            std::scanf("%lld", &A[i][j]);
        }
    }
    solve(N, K, std::move(A));
    return 0;
}

#include <bits/stdc++.h>
// #include <atcoder/all>
// #include "icld.cpp"
using namespace std;
using ll = long long int;
using vi = vector<int>;
using si = set<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using ss = string;
using db = double;
template<typename T> using minpq = priority_queue <T,vector<T>,greater<T>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
#define V vector
#define P pair<int,int>
#define PLL pair<ll,ll>
#define rep(i,s,n) for(int i=(s);i<(int)(n);i++)
#define rev(i,s,n) for(int i=(s);i>=(int)(n);i--)
#define reciv(v,n) vll (v)((n)); rep(i,0,(n))cin>>v[i]
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ci(x) cin >> x
#define cii(x) ll x;cin >> x
#define cci(x,y) ll x,y;cin >> x >> y
#define co(x) cout << x << endl
#define pb push_back
#define eb emplace_back
#define rz resize
#define pu push
#define sz(x) int(x.size())
#define vij v[i][j]
// ll p = 1e9+7;
// ll p = 998244353;
// n do -> n*pi/180
#define yn cout<<"Yes"<<endl;else cout<<"No"<<endl
#define YN cout<<"YES"<<endl;else cout<<"NO"<<endl
template<class T>void chmax(T &x,T y){x=max(x,y);}
template<class T>void chmin(T &x,T y){x=min(x,y);}

ll x,y;
ll exgcd(ll a,ll b,ll &x,ll &y){
  if(b==0){x=1;y=0;return a;}
  ll d=exgcd(b,a%b,y,x);
  y-=a/b*x;
  return d;
}

int main(){
  cii(t);
  vll ans;

  while(t--){
    cii(n);
    cci(s,k);
    s=n-s;

    ll g=__gcd(n,__gcd(s,k));
    n/=g;
    s/=g;
    k/=g;

    ll g2=__gcd(n,k);
    if(g2!=1){ans.pb(-1);continue;}
    
    exgcd(k,n,x,y);
    (x+=n)%=n;
    ans.pb(s*x%n);
  }

  for(ll d:ans)co(d);
}