#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;

//for debugging 
/*
g++ -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -std=c++14 
*/
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}
// debugging ends here

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int mod = 998244353;

int gcd(int a, int b) {
	return (b?gcd(b,a%b):a);
}

int gcdExtended(int a,int b, int *x , int *y) {
	if(a==0) {
		*x = 0;*y=1;
		return b;
	}
	int x1, y1;
	int g = gcdExtended(b%a,a,&x1,&y1);

	*x = y1- (b/a)*x1;
	*y = x1;

	return g;
}


void solve() {	
	int n,s,k;
	cin >> n >> s >> k;
	int g = gcd(n,k);
	if(s%g !=0) {
		cout << -1 << endl;
		return;
	}
	s = n-s;
	n/=g,s/=g,k/=g;

	int x,y;
	g = gcdExtended(k,n,&x,&y);
	x = (x+n)%n;
	int ans = (long long )(s)*x%n;
	cout << ans << endl;
}



int main(){
	fast;
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif

	int t;cin >> t;while(t--)
		solve();
}

#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end() //vector
#define rep(i,n) for(ll i=0; i<n; ++i)
#define REP(i,n) for(ll i=1; i<=n; ++i)
#define Rep(i,s,n) for(ll i=s; i<n; ++i)
using namespace std;
 
//最大公約数
ll gcd (ll a, ll b){
    if (b==0) return 0;
    return gcd(b,a%b);
}
//最小公倍数
ll lcm (ll a, ll b){
    return (ll)a/gcd(a,b)*b;
}
//入力はすべて正とする
//素数判定
bool is_prime (ll n){
    for (ll i=2; i*i<=n; i++){
        if (n%i==0) return false;
    }
    return true;
}
 
int main(){
  int n;
  cin >> n;
  vector<string> s(n);
  vector<ll> t(n);
  vector<ll> cp(n);
  rep(i,n){
    cin >> s.at(i) >> t.at(i);
    cp.at(i)=t.at(i);
  }
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  rep(i,n){
    if (t.at(1)==cp.at(i)){
      cout << s.at(i) << endl;
      return 0;
    }
  }
}