#include <bits/stdc++.h>
using namespace std;
using ll  = long long;
using vi  = vector<int>;
using pii = pair<int,int>;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=int(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=int(a);i>=(int)(b);i--)
const int mod  = 1e9+7;
const int maxn = 2e5+10;
const int inf  = 0x3f3f3f3f;
int main() {
#ifndef WA_DEBUG
    ios::sync_with_stdio(false);cin.tie(nullptr);
#endif
    int _;
    cin>>_;
    while(_--) {
        ll n,s,k;
        cin>>n>>s>>k;
        s=n-s;
        if(s%__gcd(k,n)) {
            cout<<-1<<'\n';
            continue;
        }
        ll x,y;
        function<ll(ll,ll,ll &,ll &)> Exgcd=[&](ll a, ll b, ll &x, ll &y) {
          if (!b) {
            x = 1;
            y = 0;
            return a;
          }
          ll d = Exgcd(b, a % b, x, y);
          ll t = x;
          x = y;
          y = t - (a / b) * y;
          return d;
        };
        Exgcd(k,n,x,y);
        x*=s/__gcd(k,n);
        y*=s/__gcd(k,n);
        ll lc=k*n/__gcd(k,n);
        ll tmp=lc/n,up=abs(y);
        //cout<<x<<' '<<y<<' '<<tmp<<'\n';
        if(y>0) {
            ll num=up/tmp;
            if(up%tmp) num++;
            x+=(lc/k*num);
        }
        else {
            ll num=up/tmp;
            x-=(lc/k*num);
        }
        cout<<x<<'\n';
    }
    return 0;
}


// Jai Shree Ram

#include<bits/stdc++.h>
typedef long long int ll;
#define pb push_back
#define max2(a,b) (a>b)?a:b
#define mi2(a,b) (a<=b)?a:b
#define fori(i,n) for(ll i=0;i<(ll)n;i++)
#define ford(i,n) for(ll i=n;i>=0;i--)
#define pll pair<ll,ll>
#define mod 1000000007
#define ff first
#define ss second
using namespace std;
#define MAXI 1e15
#define MAX_LIMIT 500001


void solve()
{
    
    ll n,m;
    cin>>n>>m;
    vector<vector<ll>> adj(n+1);
    fori(i,m)
    {
        ll a,b;
        cin>>a>>b;
        adj[a].pb(b);
    }
    ll ans=0;
    
    for(int i=1;i<=n;i++)
    {
        stack<ll> st;
        vector<bool> visited(n+1,0);
        vector<ll> covered(n+1,0);
        visited[i]=1;
        st.push(i);
        while(!st.empty())
        {
            ll tmp=st.top();
            visited[tmp]=1;
            bool fl=0;
            for(int j=covered[tmp];j<adj[tmp].size();j++)
            {
                if(!visited[adj[tmp][j]])
                {
                    fl=1;
                    covered[tmp]=j;
                    st.push(adj[tmp][j]);
                    visited[tmp]=1;
                    break;
                }
            }
            if(!fl)
            {
                ans++;
                st.pop();
            }

        }
    }
    cout<<ans<<"\n";







}
 

 
int main()
{
     

 
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);




    
    ll T;
    T=1;
    //cin>>T;
    
    fori(_,T)
    {
        solve();
    }
    
   
 
 
    
 
}
