#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;long long n,p;int main(){	int t;	scanf("%d",&t);	while(t--){		scanf("%lld%lld",&n,&p);		int a,b;		a=b=0;		for(long long  i=p;i<=n*2;i*=p)		a+=((2*n)/i);		for(long long i=p;i<=n;i*=p)		b+=(n/i);		long long  tmp=a-b-b;		printf("%lld\n",tmp>0?tmp:0);	}	return 0;}