3679. 进制转换

#define ll long long
#define IOS ios::sync_with_stdio(false)
using namespace std;
int main()
{
        IOS;cin.tie(0);
        int t;
        cin>>t;
        while(t--){
                ll l,r,k,m;
                cin>>l>>r>>k>>m;
                l-=1;
                while(m)
                { 
                        m--;
                        l=l/k;
                        r=r/k;
                }
                ll ans1=l-l/k;
                ll ans2=r-r/k;
                cout<<ans2-ans1<<endl;
        }
}