#include<iostream>
#include <cstring>
#define LL long long
using namespace std;
LL ans;
int a[1000];
int num;
void get_prime(LL n)    //快速求出所有n的质因子
{             //使用唯一分解定理 任何一个数都可以拆分成若干个质数的乘积
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			a[num++]=i;
			while(n%i==0)
				n/=i;
		}
	}
	if(n>1)         //注意最后一项的处理
		a[num++]=n;
}
LL rongchi(LL m)   //容斥原理公式
{
	LL que[10000];
	LL sum=0;
	int t=0;
	que[t++]=-1;
	for(int i=0;i<num;i++)
	{
		int k=t;
		for(int j=0;j<k;j++)
			que[t++]=(-1)*a[i]*que[j];
	}
	for(int i=1;i<t;i++)
		sum+=m/que[i];
	return sum;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int t;
	scanf("%d",&t);
	int flag=1;
	while(t--)
	{
		LL x,y;
		int n;
		scanf("%lld%lld%d",&x,&y,&n);
		memset(a,0,sizeof(a));
		ans=0,num=0;
		get_prime(n);
		ans=(y-rongchi(y))-(x-1-rongchi(x-1));
		printf("Case #%d: %lld\n",flag++,ans);
	}
	return 0;
}

#include <cstring>
#include <iostream>
#define LL long long
using namespace std;
LL n,ans;
int m,cnt;
int a[15];
LL gcd(LL a,LL b)
{
	return b==0?a:gcd(b,a%b);
}
void dfs(int cur,LL lcm,int id)
{
	lcm=a[cur]/gcd(a[cur],lcm)*lcm;
	if(id&1)
		ans+=(n-1)/lcm;
	else
		ans-=(n-1)/lcm;
	for(int i=cur+1;i<cnt;i++)
		dfs(i,lcm,id+1);
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(scanf("%lld%d",&n,&m)!=EOF)
	{
		cnt=0,ans=0;
		memset(a,0,sizeof(a));
		for(int i=0;i<m;i++)
		{
			int x;
			scanf("%d",&x);
			if(x!=0)           //x为非负数 需要把0排除
				a[cnt++]=x;
		}
		for(int i=0;i<cnt;i++)
			dfs(i,a[i],1);
		printf("%lld\n",ans);
	}
	return 0;
}

#include<cstdio>
#include<vector>
#define maxn 100050
#define LL long long
using namespace std;
vector<int>e[maxn];
int que[maxn];
void init()
{
	for(int i=0;i<maxn;i++)
		e[i].clear();
	for(int i=2;i<maxn;i++)
	{
		int t=i;
		for(int j=2;j*j<maxn;j++)
		{
			if(t%j==0)
			{
				e[i].push_back(j);
				while(t%j==0)
					t/=j;
			}
		}
		if(t>1)
			e[i].push_back(t);
	}
}
LL rongchi(int n,int s)
{
	int num=0;
	que[num++]=1;
	for(int i=0;i<e[s].size();i++)
	{
		int ep=e[s][i];
		if(ep>n)
			break;
		int k=num;
		for(int j=0;j<k;j++)
			que[num++]=que[j]*(-1)*ep;
	}
	LL sum=0;
	for(int i=0;i<num;i++)
		sum+=n/que[i];
	return sum;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	init();
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int m,n;
		scanf("%d%d",&m,&n);
		LL ans=n;
		for(int i=2;i<=m;i++)
			ans+=rongchi(n,i);
		printf("%lld\n",ans);
	}
	return 0;
}