import sys
input = sys.stdin.readline
mod = 998244353
from math import gcd


def PrimeDecomposition(N):
    ret = {}
    n = int(N ** 0.5)
    for d in range(2, n + 1):
        while N % d == 0:
            if d not in ret:
                ret[d] = 1
            else:
                ret[d] += 1
            N //= d
        if N == 1:
            break
    if N != 1:
        ret[N] = 1
    return ret


def euler_phi(N):
    P = PrimeDecomposition(N)
    ret = N
    for p in P:
        ret = ret * (p - 1) // p
    return ret


for _ in range(int(input())):
    M, A, B, K = map(int, input().split())
    if K > A:
        print(0)
        continue

    g = gcd(A, B)
    A //= g
    B //= g
    M //= g
    if K % g:
        print(0)
        continue
    K //= g

    phi = euler_phi(A)
    X = B % A
    X_inv = pow(X, phi - 1, A)

    if K == A:
        ans = (M // (A * B)) * (B - A + 1) - 1
        m = M % (A * B)
        ans += m // A - (m // B)
        a_max = (m // A) * A
        b_max = (m // B) * B
        if b_max > a_max:
            ans += 1
        print(ans)
    else:
        ans = (M // (A * B)) * 2
        i = (K * X_inv) % A
        if M % (A * B) >= B * i:
            ans += 1
        j = ((A - K) * X_inv) % A
        if M % (A * B) >= ((B * j - 1) // A + 1) * A:
            ans += 1
        print(ans)