dig

#include<bits/stdc++.h>
using namespace    std;


typedef long long int       ll;
typedef double              dl;
typedef unsigned long long  ul;

const int MX = 1e6+5;



int main()
{
   #ifndef ONLINE_JUDGE
       freopen("input.txt","r",stdin);
       freopen("out.txt","w",stdout);
   #endif

       vector<dl>v(MX);

       for(int i=1; i<MX; i++)
        {
            v[i] = v[i-1]+log10(i);
        }

   int t;
   cin>>t;
   int x=1;
   while(t--);
   {
        int n,b;
        cin>>n>>b;

        int digit = v[n] / (log10(b))+1;

        cout<<"Case "<<x++<<": "<<digit<<endl;
   }
    return 0;
}
/// ----------------------------Funaction Descriptions----------------------------------//


//author anikaksh;