#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 4000000000000000000 //オーバーフローに注意
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



ll gcd(ll x,ll y){

	x = abs(x);
	y = abs(y);

	if(x < y){
		swap(x,y);
	}
	if(y == 0){
		return x;
	}else{
		return gcd(y,x%y);
	}
}

//最小公倍数
ll lcm(ll x,ll y){

	return (x*y)/gcd(x,y);
}

ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}

void func(){

	ll N,S,K;
	scanf("%lld %lld %lld",&N,&S,&K);

	ll common = gcd(K,N);
	if(S%common != 0){

		printf("-1\n");
		return;
	}

	N /= common;
	S /= common;
	K /= common;

	S = (-S+N)%N;
	ll work = mod_inverse(K,N);

    ll ans = (S*work)%N;

    printf("%lld\n",ans);
}

int main(){

	int num_case;

	scanf("%d",&num_case);

	for(int loop = 0; loop < num_case; loop++){

		func();
	}

	return 0;
}


#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  vector<int> a(n);
  for(auto &nx : a){cin >> nx;}
  long long res1=(n*(n-1)/2);
  
  sort(a.begin(),a.end());
  a.push_back(-1);
  long long cnt=1;
  for(int i=0;i<n;i++){
    if(a[i]!=a[i+1]){
      res1-=((cnt*(cnt-1))/2);
      cnt=1;
    }
    else{cnt++;}
  }
  cout << res1 << '\n';
  //cout << res2 << '\n';
}
