#include<bits/stdc++.h>
using namespace std;
int t,l,r,n,ans;
int main() 
{
    cin>>t;
    for(int i=1;i<=t;i++)
    {
    	ans=0;
    	cin>>l>>r>>n;
        for(int j=l;j<=r;j++)
            if(__gcd(j,n)==1)
				ans++;
        cout<<ans<<endl;
    }
    return 0;
}

T掉了