#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FASTIO {ios_base::sync_with_stdio(false);cin.tie(NULL);}


//************ functions

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

ll pow(ll a,ll m){
	
    ll m0 = m; 
    ll y = 0, x = 1; 
  
    if (m == 1) 
        return 0; 
  
    while (a > 1) { 
        // q is quotient 
        ll q = a / m; 
        ll t = m; 
  
        // m is remainder now, process same as 
        // Euclid's algo 
        m = a % m, a = t; 
        t = y; 
  
        // Update y and x 
        y = x - q * y; 
        x = t; 
    } 
  
    // Make x positive 
    if (x < 0) 
        x += m0; 
  
    return x; 
}

int main(){
	FASTIO;
	//sieve();
	int t;
	cin>>t;
	while(t--){
		ll n,s,k;
		cin>>n>>s>>k;
		ll a,b,c;
		ll d=gcd(k,gcd(n-s,n));
		a=k/d;
		b=(n-s)/d;
		c=n/d;
		//cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
		if(gcd(a,c)!=1) cout<<-1;
		else{
			cout<<pow(a,c)*b%c;
		}
		cout<<endl;
	}
}

#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<set>
#include<cstdlib>
#include<cmath>
#include<numeric>//fill
#include<iomanip>
#include<functional>//https://cpprefjp.github.io/reference/functional/function.html
#include<cstdlib>//https://cpprefjp.github.io/reference/cstdlib.html
#include<queue>
#include<deque>
#include<cassert>
#include<stack>
#include <iterator>     // std::back_inserter
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
const double PI = acos(-1);
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n)for(ll i=0;i<(n);i++)
#define repp(x,arr) for(auto& x:arr)
#define repp2(x,y,arr) for(auto& [x,y]:arr)
#define all(a) (a.begin()),(a.end())
const ll MOD = 1e9 + 7;
const ll inf = (ll)1e18+6;

// デフォルトは整数部も含めた桁数指定
//cout <<setprecision();
ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}
double dl[4] = { 0,0,0.1,0.1 };
double dr[4] = { 0,-0.1,0,-0.1 };
int main() {
	ios::sync_with_stdio(false);
	//ll a, b, c, d;
	//cin >> a >> b >> c >> d;
	//if (a == 0) {
	//	cout << 0;
	//	return 0;
	//}
	//if (c <= b) {
	//	cout << -1;
	//	return 0;
	//}

	//ll aka = 0;
	//ll mizu = a;
	//ll ans = 0;
	//while (mizu > aka * d) {
	//	ans++;
	//	aka += c;
	//	mizu += b;
	//}
	//cout << ans;
	ll N;
	cin >> N;
	vector<double>l(N), r(N);
	rep(i, N) {
		int t;
		cin >>t>> l[i] >> r[i];
		t--;
		l[i] += dl[t];
		r[i] += dr[t];
	}
	ll ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if(r[j]<l[i]||r[i]<l[j])continue;
				ans++;
		}
	}
	cout << ans;

}
