#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
bool vis[100001];
int shai();
int main()
{
	int n;
	cin>>n;
	shai();
	for(int i=1;i<=n;i++)
	{
		int a,b,d,ans=0;
		cin>>a>>b>>d;
		for(int j=a;j<=b;j++)
		{
			int s,j1=j;
			if(!vis[j])
			{
				while(j1>0)
				{
					s=j1%10;
					if(s==d)
					{
						ans++;
						break;
					}
					j1/=10;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
int shai()
{
	int a=0;
	for(int i=2;i<=315;i++)
	{
		a=i*i;
		for(int j=i*i;j<=100001;j+=a)	
		{
			vis[j]=1;
		}		
	}
	return 0;
}