import sys

input = sys.stdin.readline


def solve(seed, N, K, B):
    factors = []
    multiplicity = []
    count = []
    for i in range(2, B+1):
        if B % i == 0:
            factors.append(i)
            m = 0
            while B % i == 0:
                B //= i
                m += 1
            multiplicity.append(m)
            count.append([])

    for _ in range(N+1):
        X = seed
        for i, f in enumerate(factors):
            c = 0
            while X % f == 0:
                c += 1
                X //= f
            count[i].append(c)
        seed = 1 + (seed*(seed+12345)) % 100000009

    ans = float('inf')
    for i in range(len(factors)):
        count[i].sort()
        ans = min(ans, sum(count[i][:K]) // multiplicity[i])

    return ans


def main():
    Q = int(input())
    for i in range(Q):
        print(solve(*map(int, input().split())))


if __name__ == '__main__':
    main()