#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <queue>

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
LL n,s,k;

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

void solve()
{
    scanf("%lld%lld%lld",&n,&s,&k);
    LL x,y;
    LL d = exgcd(k,n,x,y);
    n /= d;
    if(s % d) puts("-1");
    else
    {
        printf("%lld\n",(-x * (s / d) % n + n) % n);
    }
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else

    #endif // LOCAL
    int T = 1;
    scanf("%d",&T);
    while(T --)
    {
        solve();
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
int T;
long long L, R;
long long solve(int L, int R) {
    if (R < 2*L) return 0;
    long long c = R - 2*L + 1;
    return c * (c+1) / 2;
}
int main() {
    scanf("%d", &T);
    while (T --) {
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", solve(L, R));
    }
    return 0;
}
