思路：

我们发现答案就是n！能除base分解质因数的最小次数

$code$

#include<iostream>
#include<cstdio>

#define ll long long

using namespace std;

ll t;

int main() {
    
	scanf("%lld", &t);
	while(t --) {
    
		register ll n, b, ans = 0, p = 1e18;
		scanf("%lld%lld", &n, &b);
		register ll i = 2;
		while(i * i <= b) {
    
			if(b % i == 0) {
    
				register ll k = n;
				register ll sum = 0;
				while(k != 0) {
    
					sum += k / i;
					k /= i;
				}
				register ll tmp = 0;
				while(b % i == 0) {
    
					b /= i;
					tmp ++;
				}
				if(sum / tmp < p) p = sum / tmp;
			}
			i ++;
		}
		if(b != 1) {
    
			register ll k = n;
			register ll sum = 0;
			while(k != 0) {
    
				sum += k / b;
				k /= b;
			}
			p = min(p, sum);
		}
		printf("%lld\n", p);
	}
	return 0;
}