homework

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;
void gen_primes(vector<int>& primes, int max) {
	primes.resize(max + 1);
	for (int i = 2; i < primes.size(); ++i) 
		if (primes[i] == 0)
			for (int k = i; k < primes.size(); k += i) 
				++primes[k];
}

int main(int c, char* av[]) {
	vector<int> primes;
	gen_primes(primes, 1e7);
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int a, b, k;
		cin >> a >> b >> k;
		int n = 0;
		for (int v = a; v <= b; ++v) {
			if (primes[v] == k) 
				++n;
		}
		cout << "Case #" << (i + 1) << ": " << n << endl;
	}
	return 0;
}