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

double fact[1000002];

int main()
{
    int n,b,t;

    fact[0] = 0;
    for(int i=1; i<=1000000; i++)
    {
        fact[i] = fact[i-1] + log(i);
    }
    cin >> t;

    for(int i=1; i<=t; i++)
    {
        cin >> n >> b;

        int digit = (fact[n]/log(b))+1;

        cout << "Case " << i << ": " << digit << endl;
    }
    return 0;
}