#include<bits/stdc++.h>
using namespace std;
#define A(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define int int64_t
void _read();
int mod;
inline int inv(int a) {
  	a %= mod;
  	if (a < 0) a += mod;
  	int b = mod, u = 0, v = 1;
  	while (a) {
  		int t = b / a;
  		b -= t * a; swap(a, b);
  		u -= t * v; swap(u, v);
  	}
  	assert(b == 1);
  	if (u < 0) u += mod;
  	return u;
}
void test() {
	int n,s,k;
	cin >> n >> s >> k;
	mod = n;
	// kx == s;
	int d = __gcd(k,n);
	if(s % d) {
		cout << -1 << '\n';
		return;
	}
	k /= d;
	s /= d;
	n /= d;
	mod = n;
	s %= mod;
	k %= mod;
	int y = inv(k);
	int ans = (s * y) % mod;
	cout << mod - ans << '\n';
}
main () { _read(); 

	int tc;
	cin >> tc;
	while(tc--) test();
	return 0;
};

void _read() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	#ifdef LOCAL
	freopen("input.txt","r",stdin);
	#endif
}

#include<bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define ll long long int
#define f first
#define s second
using namespace  std;
ll mod=1e9+7;
struct gcd_type
{
    ll x,y,g;
};
gcd_type ext_gcd(ll a,ll b)
{
    if(b==0) return{1,0,a};
    gcd_type p= ext_gcd(b,a%b);
    return {p.y,p.x-a/b*p.y,p.g};
}
ll shift(ll a,ll add)
{
    ll l=0,r=(abs(a)/add)+5,ans;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        if(mid*add>-a)ans=mid,r=mid-1;
        else l=mid+1;
    }
    a+=ans*add;
    //cout<<ans<<">>>"<<endl;
    return a;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        ll n,s,k;
        cin>>n>>s>>k;
        gcd_type q=ext_gcd(k,n);
        if(s%q.g!=0)cout<<"-1"<<endl;
        else
        {
            q.x*=s/q.g,q.y*=s/q.g;
            ll x=q.x,y=q.y,g=q.g,lcm=(n*k)/g;
            ll num=(((y%(k/g))*(n%lcm)-s%lcm)%lcm+lcm);
           //cout<<x<<" "<<y<<" "<<num<<"::::"<<endl;
            cout<<(num%lcm)/k<<endl;
        }
    }
    return 0;
}
