import java.util.*;
import java.io.*;

public class tricks {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int S = Integer.parseInt(in.readLine());
        for (int scen=1; scen <= S; ++scen) {
            System.out.println("Scenario #"+scen+":");
            String[] tokens = in.readLine().split(" ");
            assert(tokens.length == 2);
            int b = Integer.parseInt(tokens[0]);
            int n = Integer.parseInt(tokens[1]);
            assert(2<=b && b <= 1000);
            assert(1<=n && n <= 1000000);
            
            int result = Integer.MAX_VALUE;
            for (int f=2; f <= b; ++f) {
                int exp = 0;
                while (b % f == 0) {
                    b /= f;
                    ++exp;
                }
                if (exp > 0) {
                    int nn = n;
                    int count = 0;
                    while (nn != 0) {
                        nn /= f;
                        count += nn;
                    }
                    result = Math.min(result, count/exp);
                }
            }
            System.out.println(result);
            System.out.println();
        }
    }
}
