#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repp(i, st, en) for (ll i = (ll)st; i < (ll)(en); i++)
#define repm(i, st, en) for (ll i = (ll)st; i >= (ll)(en); i--)
#define all(v) v.begin(), v.end()
void chmax(ll &x, ll y) {x = max(x,y);}
void chmin(ll &x, ll y) {x = min(x,y);}
void Yes() {cout << "Yes" << endl; exit(0);}
void No() {cout << "No" << endl; exit(0);}
template<class in_Cout> void Cout(in_Cout x) {cout << x << endl; exit(0);}
template<class in_vec_cout>
void vec_cout(vector<in_vec_cout> vec) {
    for (in_vec_cout res : vec) {cout << res << " ";}
    cout << endl;
}

const ll inf = 1e18;
const ll mod = 1e9 + 7;

/*
x*K = N - S (mod N)
*/

ll gcd(ll x, ll y) {
    if (y==0) return x;
    return gcd(y,x%y);
}

// 拡張ユークリッドの互除法 O(log(lcm(a,b)))
// a*x + b*y = gcd(a,b) となる (x,y) を返す
// b*s + (a%b)*t = gcd(a,b)
// a = (a/b)*b + a%b, d = gcd(a,b) = gcd(b,a%b)
// ((a/b)*b + a%b)*x + b*y = d
// b*((a/b)*x + y) + (a%b)*x = d
// {s = (a/b)*x + y, t = x} <=> {x = t, y = s - (a/b)*t}
pair<ll,ll> ext_gcd(ll a, ll b) {
    if (b==0) return {1,0};
    pair<ll,ll> P = ext_gcd(b, a%b);
    ll s = P.first, t = P.second;
    return {t, s-(a/b)*t};
}

ll solve() {
    ll N, S, K;
    cin >> N >> S >> K;

    ll d = gcd(N,gcd(N-S,K));
    ll A = K / d, B = (N-S) / d;
    N /= d;

    if (gcd(A,N)!=1) return -1;

    ll invA = (ext_gcd(A,N).first + N) % N;
    
    return B * invA % N;
}

int main() {
    ll T; cin >> T;
    vector<ll> res(T);
    rep(i,T) res[i] = solve();
    for (ll ans : res) cout << ans << endl;
}
#include<bits/stdc++.h>
using namespace std; 
int gcd_extend(int a, int b, 
               long long& x,long long& y) 
{ 
    // Base Case 
    if (b == 0) { 
        x = 1; 
        y = 0; 
        return a; 
    } 
  
    // Recursively find the gcd 
    else { 
        int g = gcd_extend(b, 
                           a % b, x, y); 
        int x1 = x, y1 = y; 
        x = y1; 
        y = x1 - (a / b) * y1; 
        return g; 
    } 
} 
  
// Function to print the solutions of 
// the given equations ax + by = c 
void print_solution(long long a,long long b,long long c,long long *x1,long long *y1) 
{ 
    long long x, y; 
    if (a == 0 && b == 0) { 
  
        // Condition for infinite solutions 
        if (c == 0) { 
            cout 
                << "Infinite Solutions Exist"
                << endl; 
        } 
  
        // Condition for no solutions exist 
        else { 
            cout 
                << "No Solution exists"
                << endl; 
        } 
    } 
    int gcd = gcd_extend(a, b, x, y); 
  
    // Condition for no solutions exist 
    if (c % gcd != 0) { 
        cout 
            << "No Solution exists"
            << endl; 
    } 
    else { 
  
        // Print the solution 
        /*cout << "x = " << x * (c / gcd) 
             << ", y = " << y * (c / gcd) 
             << endl; */
    	*x1=x*(c/gcd);
    	*y1=y*(c/gcd);
    } 
} 
int main(){
    // write your code
    #ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	int T;
	cin>>T;
	while(T--)
	{
		long long n,s,k,x,y;
		cin>>n>>s>>k;
		if(s%__gcd(n,k))	{cout<<"-1\n";continue;}
		int d=__gcd(n,__gcd(k,s));
		n=n/d;
		k=k/d;
		s=s/d;
		print_solution(k,n,-s,&x,&y);
		cout<<((x%n)+n)%n<<endl;
	}
}