NEFU 119

#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;
}