1 #include<stdio.h>
 2 int main()
 3 {
 4     int n,m,s,t;
 5     while(~scanf("%d",&t))
 6     {
 7         while(t--)
 8         {
 9             scanf("%d%d",&n,&m);
10             s=0;
11             while(n>=m)
12             {
13                 s+=n/m;
14                 n/=m;
15             }
16             printf("%d\n",s);
17         }
18     }
19 }