import java.util.Scanner;
import java.math.BigInteger;
public class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
while(t!=0)
{
int a=sc.nextInt();
int b=sc.nextInt();
BigInteger c=new BigInteger(β1β);
for(int i=2;i<=a;i++)
{
c=c.multiply(BigInteger.valueOf(i));
}
int d=0;
BigInteger e=new BigInteger(β0β);
while((c.mod(BigInteger.valueOf(b))).compareTo(e)==0)
{
c=c.divide(BigInteger.valueOf(b));
b=b*b;
//System.out.println(b);
//c=c.divide(BigInteger.value of(b));
d++;
}
System.out.println(d);
t--;
}
}
}