sigma (a * i + b)/c, i = 0->n

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = 2e5 + 5;
vector<int> gr[N];
pii p[N];
ll ans;
/*
f(a, b, c, n) = (a*i+b)/c, 0 <= i <= n
a < n, b < n
k = (a*n+b)/c
for(i, 0, n)
    for(j, 0, k-1)ans += (j < (a*i+b)/c)
for(j, 0, k-1)
    for(i, 0, n)ans += (j < (a*i+b)/c)
for(j, 0, k-1)
    for(i, 0, n)ans += (j*c+c <= a*i+b)
for(j, 0, k-1)
    for(i, 0, n)ans += ((j*c+c-b-1)/a < i)
for(j, 0, k-1)
    ans += n-(j*c+c-b - 1)/a;
= n*k-f(c, c-b-1 , a, k-1)
*/
ll f(ll a, ll b, ll c, ll n)
{

    if (a == 0)
        return (n + 1) * (b / c);
    if (a >= c || b >= c)
        return f(a % c, b % c, c, n) + n * (n + 1) / 2 * (a / c) + (n + 1) * (b / c);
    ll k = (a * n + b) / c;
    return n * k - f(c, c - b - 1, a, k - 1);
}
int main()
{
    ios_base::sync_with_stdio(0),
        cin.tie(0);
    int t;
    cin >> t;
    while (t-- > 0)
    {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        int k = (d - 2) / (c - b);
        ans = k - f(c, a, d, k) + f(b, a - 1, d, k);
        cout << ans << '\n';
    }
}