#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
bool isPrime[10000001];
void main_() {
#ifdef ABHISHEK_SRIVASTAVA
freopen("prime_subtractorization_input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for (int i = 2; i <= 1e7; i++)
isPrime[i] = 1;
for (int i = 2; i <= 1e7; i++)
if (isPrime[i])
for (long long j = 1ll * i * i; j <= 1e7; j += i)
isPrime[j] = 0;
vector<int> usefulPrimes;
for (int i = 2; i <= 1e7; i++)
if (isPrime[i] && isPrime[i - 2])
usefulPrimes.push_back(i - 2);
int testCases;
cin >> testCases;
for (int currentTestCase = 1; currentTestCase <= testCases; currentTestCase++)
{
int n, ind;
cin >> n;
ind = upper_bound(usefulPrimes.begin(), usefulPrimes.end(), n - 2) -
usefulPrimes.begin();
if (ind)
ind++;
cout << "Case #" << currentTestCase << ": ";
cout << ind;
cout << '\n';
}
static void run_with_stack_size(void (*func)(void), size_t stsize) {
char *stack, *send;
stack = (char *)malloc(stsize);
send = stack + stsize - 16;
send = (char *)((uintptr_t)send / 16 * 16);
asm volatile(
"mov %%esp, (%0)\n"
"mov %0, %%esp\n"
:
: "r"(send));
func();
asm volatile("mov (%0), %%esp\n" : : "r"(send));
free(stack);
}
int main() {
run_with_stack_size(main_, 1024 * 1024 * 1024);
return 0;
}
