#include<bits/stdc++.h>
using namespace std;
inline long long read(){
   long long s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int main(){
    int T;

    cin>>T;
    while(T--){
        long long n=read(),p=read(),sum=0,a;
        if(p==1) {
            cout<<0<<endl;continue;
        }
        for(int i=0;i<=n;i++){
            a=n/pow(p,i);
            if(pow(p,i)>n) break;;
            if(i%2==0){
                sum+=a;
            }
            else sum-=a;

        }
        cout<<sum<<endl;
    }
    return 0;
}

感觉复杂度在O（nlogn）阿？