typedef __int64 ll;ll gao(ll l,ll r,ll n){//[l,r]内与n互素的数字个数     vector <ll> v;    for(ll i=2;i*i<=n;i++){        if(n%i==0){            v.push_back(i);            while(n%i==0)n/=i;        }    }    if(n>1)v.push_back(n);    int m=v.size();    ll res=0;     for(ll i=1;i<(1<<m);i++){        int cnt=0;        ll val=1;        for(int j=0;j<m;j++){            if(i&(1<<j)){                cnt++;                val*=v[j];            }        }        if(cnt&1)res+=r/val-(l-1)/val;        else res-=r/val-(l-1)/val;    }    return r-l+1-res;}