#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,s,k;
 
ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
} 
 
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,x,y);
    ll z = x;
    x = y;
    y = z-(a/b)*y;
    return d;
}
 
void solve()
{
    ll a = k;
    ll b = n;
    ll m = n-s;
    ll g = gcd(a,b);
    if(m%g!=0){
        cout<<-1<<endl;
        return;
    }
    
    ll d = gcd(g,m);
    a /= d;
    m /= d;
    b /= d; 
    n /= d;
    
    ll tmp = gcd(a,b);
 
    ll x,y;
    exgcd(a,b,x,y);
    ll tm =  x*m/tmp;
  	ll res = (tm%n+n)%n;
    cout<<res<<endl;
 
    return;
}
 
int main()
{
    cin>>t;
    while(t--){
        cin>>n>>s>>k;
        solve();
    }
 
    return 0;
}
#include<bits/stdc++.h>
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define LL long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define int long long
#define sz(x) (ll)(x.size())
using namespace std;


const int mod = 1e9+7;

int expo_pow(int x,int y){
 if(y == 0) return 1;
  y=y%(mod-1);
  x%=mod;
  if(y==0) y=mod-1;
  int res=1;
  while(y){
    if(y&1) res=(res*x)%mod;
    x=(x*x)%mod;
    y>>=1; 
  }
  return res;
}

ll add()
{
    return 0;
}

template <typename T, typename... Types>
T add(T var1, Types... var2){
    return (((((ll)(var1)) % mod + (ll)(add(var2...))) % mod) + mod) % mod;
}

ll mul(){
    return 1;
}

template <typename T, typename... Types>
T mul(T var1, Types... var2){
    return (((ll)(var1)) % mod * (ll)(mul(var2...))) % mod;
}

class triplet{
    public:
    LL a;
    LL b;
    LL gcd;
};

triplet extended_euclid(LL a,LL b)
{
    if(b==0)
    {
        triplet x;
        x.a=1;
        x.b=0;
        x.gcd=a;
        return x;
    }
    triplet x1=extended_euclid(b,a%b);
    triplet x;
    x.a=x1.b;
    x.b=x1.a-(a/b)*(x1.b);
    x.gcd=x1.gcd;
    return x;
}
LL mod_inverse(LL a, LL m)
{
    LL ans=extended_euclid(a,m).a;
    return (ans%m +m )%m;
}

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

  int ans = mod_inverse(k,n);
  ans*= steps_to_move;
  ans %= n;
  ans += n;
  ans %= n;

  cout << ans << "\n";
  
}


signed main(){
  fast;
  int test = 1;
  cin>>test;
  int i=1;
  while(test--){
    solve();
  }
}



