def generate_sequence(seed, N):
    mod = 100000009
    X = [seed]
    for _ in range(N):
        prev = X[-1]
        val = (prev ** 2 + prev * 12345) % mod
        X.append(1 + val)
    return X

def factorize(B):
    factors = []
    p = 2
    while p * p <= B:
        if B % p == 0:
            count = 0
            while B % p == 0:
                count += 1
                B = B // p
            factors.append((p, count))
        p += 1
    if B > 1:
        factors.append((B, 1))
    return factors

def compute_exponents(X, factors):
    exponents = []
    for x in X:
        exps = []
        for (p, _) in factors:
            count = 0
            current_x = x
            while current_x % p == 0 and current_x != 0:
                count += 1
                current_x = current_x // p
            exps.append(count)
        exponents.append(exps)
    return exponents

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    Q = int(input[ptr])
    ptr += 1
    for _ in range(Q):
        seed = int(input[ptr])
        N = int(input[ptr+1])
        K = int(input[ptr+2])
        B = int(input[ptr+3])
        ptr +=4
        
        # Generate the X sequence
        X = generate_sequence(seed, N)
        
        # Factorize B
        factors = factorize(B)
        if not factors:
            print(0)
            continue
        
        # Compute exponents for each X_i
        exponents_list = compute_exponents(X, factors)
        m = len(factors)
        min_trailing = float('inf')
        
        # For each prime's selection (sorted by their exponents)
        for i in range(m):
            # Sort the exponents_list based on the i-th component (prime's exponents)
            sorted_exponents = sorted(exponents_list, key=lambda x: x[i])
            selected = sorted_exponents[:K]
            
            # Sum each prime's exponents in the selected elements
            sums = [0] * m
            for exp in selected:
                for j in range(m):
                    sums[j] += exp[j]
            
            # Compute trailing zeros for this selection
            current_trailing = min(sums[j] // factors[j][1] for j in range(m))
            
            if current_trailing < min_trailing:
                min_trailing = current_trailing
        
        print(min_trailing)

if __name__ == "__main__":
    main()