import java.util.HashMap;
import java.util.Iterator;
import java.util.Scanner;

public class FactorialZeros {
    static Scanner sc=new Scanner(System.in);
    public static void main(String[] args) {
        int T=sc.nextInt();
        for(int t=0;t<T;t++){
            int B=sc.nextInt();
            long N=sc.nextLong();

            HashMap<Integer,Integer> factors=new HashMap<>();
            int BB=B;

            while(BB>1){
                for(int b=2;b<BB+1;b++){
                    int pow=0;
                    while(BB%b==0){
                        pow++;
                        BB/=b;
                    }
                    if(pow>0)factors.put(b,pow);
                }
            }

            int noDistinctFactors=factors.keySet().size();
            int[] distFactors=new int[noDistinctFactors];
            int[] powers=new int[noDistinctFactors];

            Iterator<Integer> it=factors.keySet().iterator();
            int i=0;
            while(it.hasNext()){
                distFactors[i]=it.next();
                powers[i]=factors.get(distFactors[i]);
                i++;
            }


            for(int d=0;d<noDistinctFactors;d++){
                System.out.println(distFactors[d]+" "+powers[d]);
            }


            long[] intendedPowers=new long[noDistinctFactors];


            for(int d=0;d<noDistinctFactors;d++){
                intendedPowers[d]=powers[d]*N;
            }

            long[] answers=new long[noDistinctFactors];



            for(int fa=0;fa<noDistinctFactors;fa++) {
                long max = 10l*N;
                long min = 1l;


                while (max >= min) {
                    //System.out.println("DEBUG: inside the binary search");
                    long mid = (max + min) / 2;
                    long aa=f(mid,distFactors[fa]);

                    if(intendedPowers[fa]==aa){
                        answers[fa]=mid;
                        break;
                    }
                    else if(intendedPowers[fa]>aa){
                        min=mid+1;
                    }
                    else{
                        max=mid-1;
                    }
                }

                while(intendedPowers[fa]==f(answers[fa]-1,distFactors[fa])){
                    answers[fa]--;
                }

            }


            long ans=Long.MIN_VALUE;
            for(int aa=0;aa<noDistinctFactors;aa++){
                ans= Math.max(ans,answers[aa]);//System.out.println("Answer "+answers[aa]);
            }

            if(ans>0)System.out.println(ans);
            else System.out.println(-1);









        }



    }


    public static long f(long x,long p){
        long ans=0;

        while(x>=p){
            ans+=x/p;
            p*=p;
        }
        //System.out.println("DEBUG: "+x+" "+p+" "+ans);
        return ans;

    }

}