#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
typedef vector < vector<ll> > Mat;
#define fi first
#define se second
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);
void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

ll GCD(ll A, ll B){
  if (A < B) swap(A, B);
  while (A % B != 0){
    A %= B; swap(A, B);
  }
  return B;
}

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

int T;

int Solve(){
  ll N, S, K; cin >> N >> S >> K;

  ll G = GCD(GCD(N, S), K);
  N /= G; S /= G; K /= G;

  if (GCD(K, N) != 1) {
    cout << -1 << endl;
    return 0;
  }

  ll x, y; extgcd(K, N, x, y);
  while (x < 0) x += N;
  cout << x * (N - S) % N << endl;

  return 0;
}

int main(){
  cin >> T;
  for (int i = 0; i < T; i++){
    Solve();
  }

  return 0;
}
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);cout << fixed;
#define dbset(x) for(int i=0 ; i<x.size(); i++) cerr << x[i] << " "; cerr << endl;
#define inf 1000000007
#define INF 1000000000000000000LL
#define PI 3.14159265358979323846
#define mod 1000000007
#define mod1 1000696969
#define flusz fflush(stdout);
#define VI vector<int>
#define VPI vector < pair<int,int> >
#define PII pair<int, int>
#define BIT bitset<N>
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define endl '\n'
#define REP(x, y) for(int x = 0; x < (y); ++x)
#define FOR(x, y, z) for(int x = y; x <= (z); ++x)
#define FORR(x, y, z) for(int x = y; x >= (z); --x)
using namespace std;

#define int long long
#define N 200007

int test;

int n;
string s,ss;

VPI g[N];

ull dp[N]; // ilosc zapalonych w wierzcholku
ull siz[N];

ull res;

void dfs(int v,int p,ull val){
    siz[v] = 1;

    for(auto it:g[v]){
        if (it.st != p){
            dfs(it.st,v,val);

            if (it.nd&val){
                res += 1LL*(((siz[it.st] - dp[it.st]) * (siz[v] - dp[v]))%mod) * (val%mod);
                res %= mod;

                res += ((dp[v] * dp[it.st])%mod) * (val%mod);
                res %= mod;
            }else{
                res += (((siz[it.st] - dp[it.st]) * (dp[v]))%mod) * (val%mod);
                res %= mod;

                res += ((dp[it.st] * (siz[v] - dp[v]))%mod) * (val%mod);
                res %= mod;
            }

            siz[v] += siz[it.st];

            if (it.nd&val){
                dp[v] += (siz[it.st] - dp[it.st] + mod);
                dp[v] %= mod;
            }else{
                dp[v] += dp[it.st];
                dp[v] %= mod;
            }
        }
    }

    return;
}

void solve()
{
    cin >> n;

    FOR(i,1,n-1){
        ull a,b,c;

        cin >> a >> b >> c;

        g[a].eb(b,c);
        g[b].eb(a,c);
    }

    FOR(i,0,61){
        FOR(j,1,n){
            dp[j] = siz[j] = 0;
        }

        dfs(1,1,(1ll<<i));
    }

    cout << res;

    return;
}

int32_t main()
{
    boost

    test=1;

    while(test--)
    {
        solve();
    }

  return 0;
}