#include <iostream>
#include <math.h>
#include <stdio.h>
#include <vector>
#define MAX 10000000
using namespace std;
 
 
long arr[10000007];
long arr2[10000007];
void init ()
{
	for (long i=1; i<=MAX; i++)
	{
		arr[i]=1;
		arr2[i]=0;
	}
	arr[1]=0;
}
 
void sangNT ()
{
	for (long i=2; i<=sqrt(MAX); i++)
	{
		if (arr[i]==1)
		{
			for (long j=2; j<=MAX/i; j++)
			{	
				arr[j*i]=0;
			}
		}
	}
}
 
int main ()
{
	init ();
	sangNT ();
	vector <long> v;
	for (long i=1; i<=MAX; i++)
	{
		if (arr[i]==1) v.push_back(i);
	}
	for (long i=0; i<v.size(); i++)
	{
		for (long j=1; j<=MAX/v[i]; j++)
		{
			arr2[v[i]*j]++;
		}
	}
	int t;
	cin>>t;
	for (int k=1; k<=t; k++)
	{
		long A, B, K, count=0;
		cin>>A>>B>>K;
		for (long i=A; i<=B; i++)
		{
			if (arr2[i]==K) count++;
		}
		printf ("Case #%d: %ld\n", k, count);
	}
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2RlZmluZSBNQVggMTAwMDAwMDAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgpsb25nIGFyclsxMDAwMDAwN107CmxvbmcgYXJyMlsxMDAwMDAwN107CnZvaWQgaW5pdCAoKQp7Cglmb3IgKGxvbmcgaT0xOyBpPD1NQVg7IGkrKykKCXsKCQlhcnJbaV09MTsKCQlhcnIyW2ldPTA7Cgl9CglhcnJbMV09MDsKfQoKdm9pZCBzYW5nTlQgKCkKewoJZm9yIChsb25nIGk9MjsgaTw9c3FydChNQVgpOyBpKyspCgl7CgkJaWYgKGFycltpXT09MSkKCQl7CgkJCWZvciAobG9uZyBqPTI7IGo8PU1BWC9pOyBqKyspCgkJCXsJCgkJCQlhcnJbaippXT0wOwoJCQl9CgkJfQoJfQp9CgppbnQgbWFpbiAoKQp7Cglpbml0ICgpOwoJc2FuZ05UICgpOwoJdmVjdG9yIDxsb25nPiB2OwoJZm9yIChsb25nIGk9MTsgaTw9TUFYOyBpKyspCgl7CgkJaWYgKGFycltpXT09MSkgdi5wdXNoX2JhY2soaSk7Cgl9Cglmb3IgKGxvbmcgaT0wOyBpPHYuc2l6ZSgpOyBpKyspCgl7CgkJZm9yIChsb25nIGo9MTsgajw9TUFYL3ZbaV07IGorKykKCQl7CgkJCWFycjJbdltpXSpqXSsrOwoJCX0KCX0KCWludCB0OwoJY2luPj50OwoJZm9yIChpbnQgaz0xOyBrPD10OyBrKyspCgl7CgkJbG9uZyBBLCBCLCBLLCBjb3VudD0wOwoJCWNpbj4+QT4+Qj4+SzsKCQlmb3IgKGxvbmcgaT1BOyBpPD1COyBpKyspCgkJewoJCQlpZiAoYXJyMltpXT09SykgY291bnQrKzsKCQl9CgkJcHJpbnRmICgiQ2FzZSAjJWQ6ICVsZFxuIiwgaywgY291bnQpOwoJfQoJCglyZXR1cm4gMDsKfQ==

NQo1IDE1IDIKMiAxMCAxCjI0IDQyIDMKMTAwMDAwMCAxMDAwMDAwIDEKMTAwMDAwMCAxMDAwMDAwIDI=

5
5 15 2
2 10 1
24 42 3
1000000 1000000 1
1000000 1000000 2