#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ld long double
#define endl '\n'
#define pb push_back
#define sz(c) (ll)c.size()
#define mp make_pair
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define F first
#define S second
#define M 1000000007
#define PI 3.1415926535897932384
#define pii pair<ll,ll>

const ll INF=1e18;
const ll N=1e5+5;
ll mod=998244353;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<pair<ll,ll>> vp;
typedef vector<vector<ll>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<char>> vvc;


//bool isPrime(ll n){
//	if(n<=1)
//	return false;
//	if(n<=3)
//	return true;
//	if(n%2==0 || n%3==0)
//	return false;
//	for(ll i=5;i*i<=n;i=i+6)
//	{
//		if(n%i==0 || n%(i+2)==0)
//		return false;
//	}
//	return true;
//}
//ll fact(ll n) 
//{
//    ll ans=1;
//    for(ll i=1;i<=n;i++)
//	ans=(ans*i)%M ;
//	return ans;
//} 
//
//  
//
// 
//ll exp(ll x,ll n){
//	
//	ll res=1;
//	while(n>0){
//		if(n%2==1)
//		res=(res*x)%M;
//		x=(x*x)%M;
//		n=n/2;
//	}
//	return res;
//}
//
//

//ll nCr(ll n, ll k) 
//{ 
//    ll res = 1; 
//  
//    // Since C(n, k) = C(n, n-k) 
//    if(k>n-k){
//    	k=n-k;
//	}
//	
//    // Calculate value of 
//    // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1] 
//    for (ll i=0;i<k;i++) { 
//        res *= (n - i); 
//        res /= (i + 1); 
//    } 
//  
//    return res; 
//}

// nCr

//vector<ll> fact(1e6+5,0);
//void fac(){
//	fact[0]=1;
//	fact[1]=1;
//	for(ll i=2;i<1e6+5;i++){
//		fact[i] = (fact[i-1]*i)%M;
//	}
//}
//ll ncr(ll n,ll r){
//	ll num= fact[n];
//	ll den= (fact[n-r]*fact[r])%M;
//	den = exp(den,M-2);
//	return (num*den)%M;
//	
//}



void null(){
    ll n;
    cin>>n;
    map<ll,ll> mx,my;
    vi x(n),y(n);
    vp a,b;

    rep(i,0,n){
        cin>>x[i]>>y[i];
        a.pb({x[i],i});
        b.pb({y[i],i});
        mx[x[i]]++;
        my[y[i]]++;
    }
    sort(all(a),[&](auto &p,auto &q){
        if(p.F==q.F)
        return y[p.S]<y[q.S];
        return p.F<q.F;
    });
    sort(all(b),[&](auto &p,auto &q){
        if(p.F==q.F)
        return x[p.S]<x[q.S];
        return p.F<q.F;
    });
    vi ans;
    ll op1= a[n-1].F-a[0].F;
    ll op2= b[n-1].F-b[0].F;
    if(a[n-1].S ==b[n-1].S and a[0].S==b[0].S){
        ans.pb(max(op1,op2));
    }
    else{
        ans.pb(op1);
        ans.pb(op2);
    }
     
    ll op3= a[n-1].F-a[1].F;
    ll op4= b[n-1].F-b[1].F;
    if(a[n-1].S ==b[n-1].S and a[1].S==b[1].S){
        ans.pb(max(op3,op4));
    }
    else{
        ans.pb(op3);
        ans.pb(op4);
    }
   
    
    ll op5= a[n-2].F-a[0].F;
    ll op6= b[n-2].F-b[0].F;
    if(a[n-2].S ==b[n-2].S and a[0].S==b[0].S){
        ans.pb(max(op5,op6));
    }
    else{
        ans.pb(op5);
        ans.pb(op6);
    }
    // vi a={op1,op2,op3,op4,op5,op6};
    sort(all(ans));
    reverse(all(ans));
    cout<<ans[1]<<endl;


}


signed main()
{
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);    
    cout<<setprecision(4);
    cout<<fixed;
    ll t = 1;
    clock_t start, end; 
    start = clock(); 
//    fac();
 
    
//    #ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin); 
//    freopen("output.txt", "w", stdout);
//    freopen("error.txt", "w", stderr);
//    #endif
    // cin>>t;
//    compute();
    while(t--){
        null();
    }
 
    end = clock();
    double time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    //cerr<<time_taken;
}
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

//-------------------------------------------------
//--Extended GCD
//-------------------------------------------------

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


//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t; cin>>t;
    while(t--){
        ll N,S,K; cin>>N>>S>>K;
        ll g = __gcd(K,N);
        if (S%g!=0){
            cout<<"-1\n";
            continue;
        }
        N/=g; S/=g; K/=g;
        ll inv,_;
        extgcd(K,N,inv,_);
        inv=(inv+N)%N;
        cout<<inv*(N-S)%N<<"\n";
    }
    return 0;
}
