import java.util.Scanner;
public class Main{
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
while(in.hasNext()){
int s=in.nextInt();
if(s==0)break;
for(int i=0;i<=s;i++){
int n=in.nextInt();
int m=in.nextInt();
int a=0;
while(true){
a++;
if(n/Math.pow(m, a)%m!=0)
{System.out.print(a);break;}
}
}
}
}
}