K. Степень простого в факториале

Для каждого запроса найдите, в какой степени простое число $p$ входит в разложение числа $N!$ на простые множители.

Например, $10!$ делится на $2^8$, но не на $2^9$.

Первая строка содержит число запросов $q$ ($1 \le q \le 10^5$).

Каждая из следующих $q$ строк содержит числа $N$ и $p$ ($1 \le N \le 10^{12}$, $p$ — простое, $2 \le p \le 10^6$).

Для каждого запроса выведите одно число.