#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const long long mod = 1000000007;
ll gcd (ll a, ll b) {return b==0 ? a : gcd(b, a%b);}

#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp make_pair
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define debug_vector(v, n) for(int i = 0; i<n; i++)cout<< v[i] << " \n"[i == n-1]

const int maxn = 1e7;
ll divs[maxn+1], quant[9][maxn+1];
bool prime[maxn];
void sieve()
{
    for (ll i = 0; i <=maxn; i++)
      prime[i] = 1;
    for (ll p = 2; p * p <= maxn; p++)
    {
      if(prime[p] == true)
      {
        for(ll i = p; i <= maxn; i += p){
          prime[i] = false;
          divs[i]+=1;
        }
      }
    }
}

int main()
{
#ifdef LOCAL
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
#endif
    //freopen("homework_input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
    fastio
    sieve();
    for(ll i =1; i<=maxn; i++){
        for(ll j =1; j<=8; j++){
            if(divs[i] == j)
                quant[j][i] = 1;
            else
                quant[j][i] = 0;
        }
    }
    for(ll i = 1; i<=8; i++){
        quant[i][1]=quant[i][1];
        for(ll j = 2; j<=maxn; j++){
            quant[i][j]+=quant[i][j-1];
        }
    }
    int tc;
    cin >> tc;
    int i = 1;
    while(tc--){
        ll a, b, k;
        cin >> a >> b >> k;
        ll ans = 0;
        if(k > 8)cout<<"Case #"<<i<<": " << ans<<endl;
        else cout<<"Case #"<<i<<": " << quant[k][b] - quant[k][a-1]<<endl;
        i++;
    }
    return 0;
}