#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll my_gcd(ll a,ll b)
{
	if (b == 0) return a;
	return my_gcd(b,a%b);
}

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int main()
{
	int T;
	cin >> T;
	rep(i,T)
	{
		ll N,S,K;
		cin >> N >> S >> K;
		ll g = my_gcd(N,K);
		if (S % g != 0)
		{
			cout << -1 << endl;
			continue;
		}

		K = K % N;

		ll x,y;
		extGCD(K,N,x,y);
		x *= -1 * (S/g);
		ll l = N*K/g;
		ll t = l/K;
		//cout << x << endl;
		//cout << t << endl;
		if (x > 0 && x <= t)
		{
			cout << x << endl;
		}
		else
		{
			if (x < 0)
			{
				x += t * (-1) * (x/t-1);
			}
			else
			{
				x -= t * (x/t);
			}
			cout << x << endl;
		}
	}
	return 0;
}
#include <bits/stdc++.h>

using namespace std;

int t;

void exgys(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
  } else {
    exgys(b, a % b, y, x);
    y -= a / b * x;
  }
}

long long inv(long long a, long long Mod) {
  long long x, y;
  exgys(a, Mod, x, y);
  return (x % Mod + Mod) % Mod;
}

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

int main() {
  cin >> t;
  while (t--) {
    long long n, s, k;
    cin >> n >> k >> s;
    long long a = s;
    long long b = (-k + n) % n, Mod = n;
    long long gys = gcd(a, gcd(b, Mod));
    a /= gys;
    b /= gys;
    Mod /= gys;
    if (gcd(a, Mod) != 1)
      cout << "-1" << endl;
    else
      cout << inv(a, Mod) * b % Mod << endl;
  }
  return 0;
}