代码如下

#include<iostream>
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;
}
bool check(unsigned long long n, int p){
	int cnt = 0;
	while(!(n % p)){
        cnt ++;
        n /= p;
    }
    return !(cnt % 2);
}
int main(){
	int t;
	cin >> t;
	while(t--){
		unsigned long long n = read(), p = read();
		long long ans = n - n / p;
		for(unsigned long long i = p; i <= n; i += p){
			ans += check(i, p);
		}
		printf("%lld\n", ans);
	}
	
}