#include<bits/stdc++.h>
using namespace std;
double a[1000010]={0};
int main()
{
    int t,n,b,c,i,j,k,l;
    for(i=1;i<=1000000;i++)
    {
        a[i]=a[i-1]+log(i);
    }
    cin>>t;
    for(i=1;i<=t;i++)
    {
        cin>>n>>b;
        long long d=1+a[n]/log(b);
        printf("Case %d: %lld\n",i,d);
    }
    return 0;
}