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

using P = pair<int64_t, int64_t>;

int64_t my_abs(int64_t a) { return max(a, -a); }

int64_t gcd(int64_t a, int64_t b) {
  while (b != 0) {
    int64_t tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}

P calc(int64_t a, int64_t b) {
  int64_t aa = my_abs(a);
  int64_t ab = my_abs(b);
  int64_t ta = aa;
  int64_t tb = ab;
  map<int64_t, int64_t> m;
  m[ta] = 1;
  m[tb] = 0;
  while (tb != 1) {
    int64_t tmp = ta % tb;
    m[tmp] = m.at(ta) - m.at(tb) * (ta / tb);
    ta = tb;
    tb = tmp;
  }
  int64_t x = m.at(1);
  if (aa == -a) {
    x *= -1;
  }
  int64_t y = (1 - x * a) / b;
  return make_pair(x, y);
}

int64_t div_ceil(int64_t a, int64_t b) {
  if (a >= 0) {
    return (a + b - 1) / b;
  } else {
    return a / b;
  }
}

int main() {
  int T;
  cin >> T;
  for (int i = 0; i < T; i++) {
    int64_t N, S, K;
    cin >> N >> S >> K;
    int64_t g = gcd(N, K);
    if (S % g != 0) {
      cout << -1 << endl;
      continue;
    }
    int64_t n = N / g;
    int64_t s = S / g;
    int64_t k = K / g;
    int64_t tx, ty;
    tie(tx, ty) = calc(n, -k);
    tx *= s;
    ty *= s;
    int64_t m = max(div_ceil(1 - tx, k), div_ceil(1 - ty, n));
    cout << n * m + ty << endl;
  }
  return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
#include<cassert>
#include<set>
#include<complex>
#include<numeric>
#include<functional>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
    for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
    for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){
    if(vec_n==-1)vec_n=vec_s.size();
    for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}
void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){
    if(vec_n==-1)vec_n=vec_s.size();
    for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}

void init(){
    
}

long long int gcd(long long int a,long long int b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    return gcd(b,a%b);
}

void solve(){
    LL n,m;
    int i,j,k;
    LL a,b,c;
    LL p,q;
    const LL B=4e4;
    cin>>n>>p>>q;
    map<LL,LL> m1;
    q%=n;
    a=q*B%n,b=0;
    for(i=0;i<B;i++,b-=a){
        if(b<0)b+=n;
        if(m1.find(b)!=m1.end())break;
        m1[b]=i;
    }
    LL s=0;
    a=p;
    for(i=0;i<B;i++,a+=q){
        if(a>=n)a%=n;
        if(m1.find(a)!=m1.end()){
            s=i+B*m1[a];
            break;
        }
    }
    if(i>=B){
        cout<<-1<<endl;
        return;
    }
    a=gcd(n,q);
    s%=n/a;
    cout<<s<<endl;
    return;
}

int main(){
    int n,i;
    init();
    cin>>n;
    for(i=0;i<n;i++){
        solve();
    }
}