#include <bits/stdc++.h>

using namespace std;

using ll = long long int;

// aの逆元を計算する
ll modinv(ll a, ll mod)
{
    ll b = mod, u = 1, v = 0;
    while (b)
    {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= mod;
    if (u < 0)
        u += mod;
    return u;
}

int main()
{
    int T;
    cin >> T;

    for (int i = 0; i < T; i++)
    {
        ll N, S, K;
        cin >> N >> S >> K;

        if (__gcd(K, N) != 1)
        {
            ll g = __gcd(K, N);

            if (S % g != 0)
            {
                cout << "-1" << endl;
                continue;
            }

            K /= g;
            N /= g;
            S /= g;
        }

        ll K_inv = modinv(K, N);

        cout << ((N - S) * K_inv) % N << endl;
    }

    return 0;
}

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

#define ll long long
#define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i)
#define rep(i, n) drep(i, 0, n - 1)
#define P pair<ll, ll>

int main(){
    ll T;
    cin >> T;

    vector<ll> L(T), R(T);
    rep(i, T) cin >> L.at(i) >> R.at(i);
    rep(i, T){
        if(R.at(i)-L.at(i) < L.at(i)){
            cout << 0 << endl;
            continue;
        }
        cout << (R.at(i)-2*L.at(i)+1)*(R.at(i)-L.at(i)+1) 
                - (R.at(i)-L.at(i))*(R.at(i)-L.at(i)+1)/2
                + (L.at(i)-1)*L.at(i)/2 << endl;
    }
}