LOJ- 1045

#include<bits/stdc++.h>
using namespace std;
typedef long long           ll;
typedef unsigned long long  ull;

#define testcase            int t; cin>>t; while (t--)
#define sc(a)               scanf("%lld",&a)
#define sc2(a,b)            scanf("%lld %lld",&a,&b)
#define reversed(s)         reverse(s.begin(), s.end())
#define asort(s)            sort(s.begin(), s.end())
#define dsort(s)            sort(s.begin(), s.end(),greater<ll>())
#define gtl(x)              getline(cin, (x))
#define PI                  acos(-1)
#define Precision(a)        cout << fixed << setprecision(a)
#define FasterIo            ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                "\n"

template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);}
template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}

int main()
{
    FasterIo
    int cas=1;
    double x=0;
    vector <double> loog(1000005);
    for(int i=1; i<=1000000; i++)
    {
        x+=log(i);
        loog[i]=x;
        //loog[i] = log(i) + loog[i-1];
        //x+=log2(i);
        //loog.push_back(x);
    }
    testcase
    {
        int n, b;
        cin >> n >> b;
        ll ans = (loog[n]/log(b))+1;
        printf("Case %d: %d\n", cas++, ans);
    }
    return 0;
}