#include <bits/stdc++.h>
using namespace std;
int main() {
int t,a,b,k,i,j,ctr,arr[1000001];
cin>>t;
memset(arr, 0, 1000001*sizeof(arr[0]));
for(i=2;i<=(1000);i++)
{
{
if(arr[i]==0)
for(j=2*i;j<=1000000;j+=i)
arr[j]++;
}
}
while(t--)
{
ctr=0;
cin>>a>>b>>k;
for(i=a;i<=b;i++)
{
if(k==1)
{
if(arr[i]==1||arr[i]==0&&i!=1)
ctr++;
}
else
{
if(arr[i]==k)
ctr++;
}
}
cout<<ctr<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKaW50IG1haW4oKSB7CglpbnQgdCxhLGIsayxpLGosY3RyLGFyclsxMDAwMDAxXTsKCWNpbj4+dDsKCW1lbXNldChhcnIsIDAsIDEwMDAwMDEqc2l6ZW9mKGFyclswXSkpOwoJZm9yKGk9MjtpPD0oMTAwMCk7aSsrKQoJewoJCQoJCXsKCQkJaWYoYXJyW2ldPT0wKQoJCQlmb3Ioaj0yKmk7ajw9MTAwMDAwMDtqKz1pKQoJCQlhcnJbal0rKzsKCQl9Cgl9CiAgICAKCXdoaWxlKHQtLSkKCXsKCQljdHI9MDsKCQljaW4+PmE+PmI+Pms7CgkJZm9yKGk9YTtpPD1iO2krKykKCQl7ICAKCQkJaWYoaz09MSkKCQkJewoJCQkJaWYoYXJyW2ldPT0xfHxhcnJbaV09PTAmJmkhPTEpCgkJCQljdHIrKzsKCQkJfQoJCQllbHNlIAoJCQl7IAoJCQkJaWYoYXJyW2ldPT1rKQoJCQkJY3RyKys7CgkJCX0KCQl9CgkJY291dDw8Y3RyPDxlbmRsOwoJfQoJcmV0dXJuIDA7Cn0g