#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, s, n) for (ll i = s; i < (n); i++)

tuple<ll, ll, ll> extgcd(ll a, ll b){
  if (b == 0) return {a,1,0};
  ll g, x, y;
  tie(g, x, y) = extgcd(b, a%b);
  return {g, y, x-a/b*y};
}

void solve(){
  ll n, s, k;
  cin >> n >> s >> k;
  ll g, x, y;
  tie(g,x,y) = extgcd(k, n);
  if (s%g != 0){
    cout << -1 << endl;
    return;
  }
  n /= g;
  s /= g;
  k /= g;
  ll ans = ((x*-s)%n+n)%n;
  cout << ans << endl;
}

int main(){
  int t;
  cin >> t;
  rep(i, t) solve();
  
  return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define OUT(V) for(int i=0;i<(int)V.size();++i){cout<<V[i]<<" ";}cout<<endl;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll MOD = 1000000007;
int main() {
    int N, M;
    cin >> N >> M;
    map<int, ll> mp;
    REP(i, N) {
        string S;
        cin >> S;
        int cnt = 0;
        REP(j, S.size()) {
            if(S[j] == '1')cnt++;
        }
        mp[cnt % 2]++;
    }
    cout << mp[0] * mp[1] << endl;
}