def prime_factors(k):
    factors = {}
    d = 2
    while d * d <= k:
        while k % d == 0:
            factors[d] = factors.get(d, 0) + 1
            k //= d
        d += 1
    if k > 1:
        factors[k] = 1
    return factors

def count_p_in_factorial(n, p):
    count = 0
    power = p
    while power <= n:
        count += n // power
        power *= p
    return count

def max_power_that_divides(n, k):
    if k == 1:
        return float('inf')
    factors = prime_factors(k)
    min_i = float('inf')
    for p, a in factors.items():
        count_p = count_p_in_factorial(n, p)
        min_i = min(min_i, count_p // a)
    return min_i

def main():
    import sys
    input = sys.stdin.read
    data = input().split()

    t = int(data[0])
    idx = 1
    results = []

    for _ in range(t):
        n = int(data[idx])
        k = int(data[idx + 1])
        idx += 2
        results.append(str(max_power_that_divides(n, k)))

    print('\n'.join(results))

if __name__ == "__main__":
    main()