#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int mod = 998244353, inv2 = (mod + 1) >> 1, inv6 = 166374059;
int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
namespace EuclidLike
{
ll calc(ll a, ll b, ll c, ll n)
{
if (a == 0)
return (n + 1) * (b / c);
if (a >= c || b >= c)
return (calc(a % c, b % c, c, n) + (a / c) * n * (n + 1) / 2 + (b / c) * (n + 1));
ll m = (a * n + b) / c;
return (n * m - calc(c, c - b - 1, a, m - 1));
}
} // namespace EuclidLike
void solve()
{
int A, B,C,D, n;
cin >> A >> B >> C >>D;
n = (D-2)/(C-B);
auto z1=EuclidLike::calc(C, A, D,n);
auto z2=EuclidLike::calc(B, A-1, D,n);
int ans = n - (z1 - z2)-(A%D==0);
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T ;
cin >> T;
while (T--)
{
solve();
}
}