using namespace std;
typedef long long ll;
int digits[35], len;
// ll mem[39][39][40][2];
/*
ll dfs(int k, int start, int pos, int s, bool limit)
{
  if (pos == -1) {
    return s;
  }
  if (!limit && mem[k][start][pos][s] != -1) {
    return mem[k][start][pos][s];
  }
  int maxi = limit ? digits[pos] : k - 1;
  ll ans = 0;
  for (int i = 0; i <= maxi; ++i) {
    tmpDigits[pos] = i;
    if (pos == start && i == 0) {
      ans += dfs(k, start - 1, pos - 1, s, limit && i == maxi);
    } else {
      if (s == 1 && pos <= (start - 1) / 2) {
        ans += dfs(k, start, pos - 1, tmpDigits[start - pos] == i, limit && i == maxi);
      } else {
        ans += dfs(k, start, pos - 1, s, limit && i == maxi);
      }
    }
  }
  if (!limit) mem[k][start][pos][s] = ans;
  return ans;
}
ll solve(int n, int k)
{
  len = 0;
  while (n) {
    digits[len++] = n % k;
    n /= k;
  }
  return dfs(k, len - 1, len - 1, 1, true);
}
*/
ll (int n, int k)
{
  len = 0;
  while (n) {
    digits[len++] = n % k;
    n /= k;
  }
  ll ret = 1;
  for (int i = len / 2, j = len - 1 - i; i < len; ++i, --j) {
    if (digits[i] != digits[j]) {
      if (digits[i] > digits[j]) --ret;
      break;
    }
  }
  ll tmpNum = 0;
  for (int i = len - 1; i >= len / 2; --i) {
    tmpNum = tmpNum * k + digits[i];
  }
  ret += tmpNum;
  tmpNum = 0;
  for (int i = len / 2; i > 0; --i) {
    tmpNum = tmpNum * k + (k - 1);
  }
  ret += tmpNum;
  return ret;
}
int main()
{
  // memset(mem, -1, sizeof mem);
  int T; scanf("%d", &T);
  for (int ca = 1; ca <= T; ++ca) {
    int L, R, l, r;
    scanf("%d%d%d%d", &L, &R, &l, &r);
    ll ans = 0;
    for (int i = l; i <= r; ++i) {
      // ll tmpN = solve(R, i);
      ll tmpN = solve2(R, i);
      ans += tmpN * (i - 1) + R;
      // tmpN = solve(L - 1, i);
      tmpN = solve2(L - 1, i);
      ans -= tmpN * (i - 1) + L - 1;
    }
    printf("Case #%d: %I64dn", ca, ans);
  }
  return 0;
}