#include<bits/stdc++.h>
using namespace std;
#define ll long long

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--) {
        ll n,s,k;
        cin>>n>>s>>k;
        ll x,y;
        x=0,y=0;
        ll g=__gcd(n,k);
        if(s%g!=0) {
            cout<<"-1"<<endl;
        }
        else {
            k/=g;
            n/=g;
            s/=g;
            ll a=(-s+n)%n;
            ll kk=gcd(k,n,x,y);
            ll b=x;
            cout<<((a*(b%n))%n+n)%n<<endl;
        }
    }
}
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

#define ll long long
#define ld long double
#define mod 1000000007
#define pb push_back
#define inf 1000000000000000000
#define ff first
#define ss second
#define deb(x) cout<<#x<<" "<<x<<"\n"
#define Clear(x) memset(x,0,sizeof(x))
#define all(x) (x).begin(),(x).end()

void checkpoint1()
{
    /******think more code less******/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("Error.txt", "w", stderr);
    #endif
}

bool comp(pair< ll,ll > &a,pair< ll,ll > &b)
{
    if(a.ff!=b.ff)
        return a.ff<b.ff;
    else
    {
        if(a.ss>b.ss)
            return b.ss<a.ss;
        else if(a.ss<b.ss)
            return a.ss<b.ss;
    }
    return a.ff>b.ff;
}

ll powe(ll a,ll b)
{
    ll res=1;
    while(b>0)
    {
        if(b&1)
        {
            res*=a;
            res%=mod;
        }
        a*=a;
        a%=mod;
        b>>=1;
    }
    return res;
}

void terminAtor()
{
    ll n;
    cin>>n;
    ll a[n];
    ll ans=0,idx=0;
    for(ll i=0;i<n;i++)
        cin>>a[i];
    for(ll i=2;i<=1000;i++)
    {
        ll op=0;
        for(ll j=0;j<n;j++)
        {
            ll oo=a[j]%i;
            if(oo==0)
                op++;
        }
        if(op>ans)
        {
            ans=op;
            idx=i;
        }
    }
    cout<<idx;
}

int main()
{    
    checkpoint1();
/********************************************************/    
    auto startrrr = high_resolution_clock::now();
    cout << setprecision(20);
/*******************************************************/    
    
    terminAtor();


/*******************************************************/    
    auto stoprrr = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stoprrr - startrrr);
    #ifndef ONLINE_JUDGE
        cerr << "Time: " << duration.count()/1000.0<<"\n";
    #endif
/*******************************************************/        
    return 0;
}