Untitled

#include <iostream>
#include <map>
#include <vector>
#include <algorithm> // for upper_bound
#include <cstring> // for memset

using namespace std;

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long long t;
    cin >> t;
    long long _t = 1;
    int n = 1e7; // Reduced size to 10^7
    bool prime[n+1]; // Changed size to 10^7+1
    memset(prime, true, sizeof(prime));
    vector<int> primes;
    
    // Sieve of Eratosthenes to find all primes <= n
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            // Mark multiples of p as false
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    
    // Collect all primes in the vector
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            primes.push_back(p);
        }
    }

    map<int, int> mp;
    mp[5] = 2;
    mp[7] = 3;
    int cnt = 3;
    for(int i = 5; i < primes.size(); i++){
        if(primes[i] == primes[i-1] + 2){ // Looking for twin primes
            mp[primes[i]] = ++cnt;
        }
    }

    while(t--){
        long long n;
        cin >> n;
        
        // Get index of the largest prime <= n
        int p = upper_bound(primes.begin(), primes.end(), n) - primes.begin();
        p--; // Move to the last prime <= n
        
        // Ensure p is within bounds
        if (p < 0 || p >= primes.size()) {
            cout << "Case #" << _t++ << ": " << 0 << endl; // Default case, handle properly
            continue;
        }

        cout << "Case #" << _t++ << ": " << mp[primes[p]] << endl;
    }
    
    return 0;
}