#include<bits/stdc++.h> using namespace std; template<typename T>void in(T &a){ T ans=0; char c=getchar(); for(;c<'0'||c>'9';c=getchar()); for(;c>='0'&&c<='9';c=getchar()) ans=ans*10+c-'0'; a=ans; } int prime[10000005],cnt,d[30000005],low[30000005],q,r,t[581][52088]; bool a[30000005]; int query(int pos,int k,int ans=0){ if(pos>=576)ans=t[k][pos/576-1]; for(int i=pos/576*576;i<=pos;i++) ans+=d[i]==k; return ans; } int main(){ d[1]=1,in(q),in(r); for(int i=2;i<=r;i++) a[i]=1; for(int i=2;i<=r;i++){ if(a[i])prime[++cnt]=i,d[i]=2,low[i]=1; for(int j=1;j<=cnt&&i*prime[j]<=r;j++){ a[i*prime[j]]=0; if(i%prime[j]==0){ low[i*prime[j]]=low[i]+1,d[i*prime[j]]=d[i/(int)pow(prime[j],low[i])]*(low[i]+2); break; } else low[i*prime[j]]=1,d[i*prime[j]]=d[i]*d[prime[j]]; } } for(int i=1;i<=r;i++) t[d[i]][i/576]++; for(int i=1;i<=576;i++){ for(int j=1;j<=52084;j++) t[i][j]+=t[i][j-1]; } for(int i=1,l,r,k;i<=q;i++){ in(l),in(r),in(k); if(k>576)puts("0"); else printf("%d\n",query(r,k)-query(l-1,k)); } return 0; }