import macros
macro Please(x): untyped = nnkStmtList.newTree()

Please use Nim-ACL
Please use Nim-ACL
Please use Nim-ACL



#[ include daylight/base ]#
when not declared DAYLIGHT_BASE_HPP:
    const DAYLIGHT_BASE_HPP* = 1
    import system
    import macros
    import algorithm
    import tables
    import sets
    import lists
    import intsets
    import critbits
    import sequtils
    import strutils
    import std/math
    import strformat
    import sugar
    let readToken* = iterator(oneChar: bool = false): string {.closure.}= 
        while true:
            var line = stdin.readLine.split
            for s in line:
                if oneChar:
                    for i in 0..<s.len():
                        yield s[i..i]
                else:
                    yield s
    proc read*(t: typedesc[string]): string = 
        result = readToken()
        while result == "":
            result = readToken()
    proc read*(t: typedesc[int]): int = read(string).parseInt
    proc read*(t: typedesc[float]): float = read(string).parseFloat
    proc read*(t: typedesc[char]): char = readToken(true)[0]

    macro readSeq*(t: typedesc, n: varargs[int]): untyped =
        var repStr = ""
        for arg in n:
            repStr &= &"({arg.repr}).newSeqWith "
        parseExpr(&"{repStr}read({t})")
    
    macro read*(ts: varargs[auto]): untyped=
        var tupStr = ""
        for t in ts:
            tupStr &= &"read({t.repr}),"
        parseExpr(&"({tupStr})")
        
    macro readTupleSeq*(n: int, ts:varargs[auto]): untyped=
        for typ in ts:
            if typ.typeKind != ntyAnything:
                error("Expected typedesc, got " & typ.repr, typ)
        parseExpr(&"({n.repr}).newSeqWith read({ts.repr})")
        
    macro initSeq*(t: typedesc, n: varargs[int]): untyped =
        var repStr = ""
        for i, arg in n:
            if i == n.len - 1:
                repStr &= &"newSeq[{t}]({arg.repr}) "
            else:
                repStr &= &"({arg.repr}).newSeqWith "
        parseExpr(repStr)
    
    
    proc `-`*(a,b: char): int = ord(a) - ord(b)
    proc `+`*(a: char,b: int): char = char(ord(a) + b)
    proc `-`*(a: char,b: int): char = char(ord(a) - b)
    proc `++`*(a: var int) = a += 1
    proc `--`*(a: var int) = a += 1

    proc chmin*[T](a: var T, b: T): bool {.discardable.} =
        if a > b:
            a = b
            return true
        return false
    
    proc chmax*[T](a: var T, b: T): bool {.discardable.} =
        if a < b:
            a = b
            return true
        return false
    const INF* = (1e9+100).int
    const LINF* = (4e18 + 100).int
    discard

#[ import atcoder/math as atcodermath ]#
when not declared ATCODER_MATH_HPP:
    const ATCODER_MATH_HPP* = 1

    #[ import atcoder/internal_math ]#
    when not declared ATCODER_INTERNAL_MATH_HPP:
        const ATCODER_INTERNAL_MATH_HPP* = 1
        import std/math
    
        type Barrett* = object
            m*, im*:uint
    
        proc initBarrett*(m:uint):auto = Barrett(m:m, im:cast[uint](-1) div m + 1)
    
        proc umod*(self: Barrett):uint =
            self.m
    
        {.emit: """
    inline unsigned long long calc_mul(const unsigned long long &a, const unsigned long long &b){
        return (unsigned long long)(((unsigned __int128)(a)*b) >> 64);
    }
    """.}
        proc calc_mul*(a,b:culonglong):culonglong {.importcpp: "calc_mul(#,#)", nodecl, inline.}
        proc quo*(self: Barrett, n:int | uint):int =
            let n = n.uint
            let x = calc_mul(n.culonglong, self.im.culonglong).uint
            let r = n - x * self.m
            return int(if self.m <= r: x - 1 else: x)
        proc rem*(self: Barrett, n:int | uint):int =
            let n = n.uint
            let x = calc_mul(n.culonglong, self.im.culonglong).uint
            let r = n - x * self.m
            return int(if self.m <= r: r + self.m else: r)
        proc quorem*(self: Barrett, n:int | uint):(int, int) =
            let n = n.uint
            let x = calc_mul(n.culonglong, self.im.culonglong).uint
            let r = n - x * self.m
            return if self.m <= r: (int(x - 1), int(r + self.m)) else: (int(x), int(r))
    
        proc pow*(self: Barrett, n:uint | int, p:int):int =
            var
                a = self.rem(n)
                r:uint = if self.m == 1: 0 else: 1
                p = p
            while p > 0:
                if (p and 1) != 0: r = self.mul(r, a.uint)
                a = self.mul(a.uint, a.uint).int
                p = p shr 1
            return int(r)
    
        proc mul*(self: Barrett, a:uint, b:uint):uint {.inline.} =
    
            let z = a * b
            return self.rem(z).uint
    
        proc pow_mod_constexpr*(x, n, m:int):int =
            if m == 1: return 0
            var
                r = 1
                y = floorMod(x, m)
                n = n
            while n != 0:
                if (n and 1) != 0: r = (r * y) mod m
                y = (y * y) mod m
                n = n shr 1
            return r.int
        
        proc is_prime_constexpr*(n:int):bool =
            if n <= 1: return false
            if n == 2 or n == 7 or n == 61: return true
            if n mod 2 == 0: return false
            var d = n - 1
            while d mod 2 == 0: d = d div 2
            for a in [2, 7, 61]:
                var
                    t = d
                    y = pow_mod_constexpr(a, t, n)
                while t != n - 1 and y != 1 and y != n - 1:
                    y = y * y mod n
                    t =    t shl 1
                if y != n - 1 and t mod 2 == 0:
                    return false
            return true
        proc is_prime*[n:static[int]]():bool = is_prime_constexpr(n)
        proc inv_gcd*(a, b:int):(int,int) =
            var a = floorMod(a, b)
            if a == 0: return (b, 0)
        
            var
                s = b
                t = a
                m0 = 0
                m1 = 1
        
            while t != 0:
                var u = s div t
                s -= t * u;
                m0 -= m1 * u;    # |m1 * u| <= |m1| * s <= b
        
        
                var tmp = s
                s = t;t = tmp;
                tmp = m0;m0 = m1;m1 = tmp;
            if m0 < 0: m0 += b div s
            return (s, m0)
    
        proc primitive_root_constexpr*(m:int):int =
            if m == 2: return 1
            if m == 167772161: return 3
            if m == 469762049: return 3
            if m == 754974721: return 11
            if m == 998244353: return 3
            var divs:array[20, int]
            divs[0] = 2
            var cnt = 1
            var x = (m - 1) div 2
            while x mod 2 == 0: x = x div 2
            var i = 3
            while i * i <= x:
                if x mod i == 0:
                    divs[cnt] = i
                    cnt.inc
                    while x mod i == 0:
                        x = x div i
                i += 2
            if x > 1:
                divs[cnt] = x
                cnt.inc
            var g = 2
            while true:
                var ok = true
                for i in 0..<cnt:
                    if pow_mod_constexpr(g, (m - 1) div divs[i], m) == 1:
                        ok = false
                        break
                if ok: return g
                g.inc
        proc primitive_root*[m:static[int]]():auto =
            primitive_root_constexpr(m)
    
        proc floor_sum_unsigned*(n, m, a, b:uint):uint =
            result = 0
            var (n, m, a, b) = (n, m, a, b)
            while true:
                if a >= m:
                    result += n * (n - 1) div 2 * (a div m)
                    a = a mod m
                if b >= m:
                    result += n * (b div m)
                    b = b mod m
    
                let y_max = a * n + b
                if y_max < m: break
                n = y_max div m
                b = y_max mod m
                swap(m, a)
        discard
    import std/math as math_lib_of_math

    proc pow_mod*(x,n,m:int):int =
        assert 0 <= n and 1 <= m
        if m == 1: return 0
        let bt = initBarrett(m.uint)
        var
            r = 1.uint
            y = x.floorMod(m).uint
            n = n
        while n != 0:
            if (n and 1) != 0: r = bt.mul(r, y)
            y = bt.mul(y, y)
            n = n shr 1
        return r.int
    
    proc inv_mod*(x, m:int):int =
        assert 1 <= m
        let z = inv_gcd(x, m)
        assert z[0] == 1
        return z[1]
    
    proc crt*(r, m:openArray[int]):(int,int) =
        assert r.len == m.len
        let n = r.len
        var (r0, m0) = (0, 1)
        for i in 0..<n:
            assert 1 <= m[i]
            var
                r1 = floorMod(r[i], m[i])
                m1 = m[i]
            if m0 < m1:
                swap(r0, r1)
                swap(m0, m1)
            if m0 mod m1 == 0:
                if r0 mod m1 != r1: return (0, 0)
                continue
    
    
            let
                (g, im) = inv_gcd(m0, m1)
                u1 = m1 div g
            if ((r1 - r0) mod g) != 0: return (0, 0)
    
            let x = (r1 - r0) div g mod u1 * im mod u1
    
            r0 += x * m0
            m0 *= u1    # -> lcm(m0, m1)
            if r0 < 0: r0 += m0
        return (r0, m0)

    proc floor_sum*(n, m, a, b:int):int =
        assert n in 0..<(1 shl 32)
        assert m in 1..<(1 shl 32)
        var (a, b) = (a, b)
        var ans = 0.uint
        if a < 0:
            var a2:uint = floorMod(a, m).uint
            ans -= n.uint * (n - 1).uint div 2 * ((a2 - a.uint) div m.uint)
            a = a2.int
        if b < 0:
            var b2:uint = floorMod(b, m).uint
            ans -= n.uint * ((b2 - b.uint) div m.uint)
            b = b2.int
        return cast[int](ans + floor_sum_unsigned(n.uint, m.uint, a.uint, b.uint))
    discard

proc solve() =
    var
        T = read(int)
    for _ in 0..<T:
        var
            (M, A, B, K) = read(int, int, int, int)
        if K > A:
            echo 0
            continue
        if K == A:
            var
                ans = 0
            ans += M div A + M div B - M div lcm(A, B) - 1
            ans -= 2 * (M div B - M div lcm(A, B))
            if (M div A) * A < (M div B) * B:
                ans += 1
            echo ans
            continue
        var (Y, Z) = crt(@[0, K], @[A, B])
        if Z == 0:
            echo 0
            continue
        var ans = M div Z
        if M mod Z >= Y:
            ans += 1
        (Y, Z) = crt(@[0, K], @[B, A])
        if Z == 0:
            echo 0
            continue
        ans += M div Z
        if M mod Z >= Y:
            ans += 1
        echo ans

solve()