#include using namespace std; using ll = long long; #include using namespace atcoder; // M 以下の正の整数のうち、A で割ったあまりが C となるものの個数 ll f(ll M, ll A, ll C) { if (C != 0) M += A - C; return max(0LL, M / A); } ll solve(ll M, ll A, ll B, ll K) { ll g = gcd(A, B); if (K % g != 0) return 0; M /= g, A /= g, B /= g, K /= g; if (K > A) return 0; else if (K == A) { ll cnt_A = f(M, A, 0), cnt_B = f(M, B, 0), cnt_AB = f(M, A * B, 0); ll N = cnt_A + cnt_B - cnt_AB; ll cnt_notA = cnt_B - cnt_AB; ll X_N = M / A * A; if (X_N % A == 0) return (N - 1) - (2 * cnt_notA); else return (N - 1) - (2 * cnt_notA - 1); } else { ll Y = crt({0, -K}, {A, B}).first; ll Z = crt({-K, 0}, {A, B}).first; return f(M - K, A * B, Y) + f(M - K, A * B, Z); } } int main() { int T; cin >> T; while (T--) { ll M, A, B, K; cin >> M >> A >> B >> K; cout << solve(M, A, B, K) << endl; } }