#include <bits/stdc++.h>
double fuck[1000000];
int main() {
  int T, j = 1, i, x, y;
  double digit;
  fuck[0] = 0;
  fuck[1] = 0;
  for (i = 2; i <= 1000000; i++) {
    fuck[i] = (double)log(i) + fuck[i - 1];
  }
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &x, &y);
    digit = 0.0;
    digit = ceil(fuck[x] / (double)log(y));
    if (digit == 0) digit = 1;
    printf("Case %d: %d\n", j, (int)digit);
    j++;
  }
  return 0;
}
