Factorials and Powers

A war has broken out in the Land of Mathematics. The Factorial faction and the Power faction are fighting to decide who will rule the land.

The Factorial faction's renowned general $n$ trains by computing his own factorial, growing as strong as $n!$, while the Power faction's admiral $k$ prepares an exponent $i$ so as to raise himself to the $i$-th power, growing as strong as $k^i$.

At last, today is the day $n$ and $k$ clash. Admiral $k$ has trained for years to divide general $n$ down into a smaller number.

Since both have grown through training, the fight is really between $n!$ and $k^i$. Write a program that finds the largest $i$ such that $n!$ is divisible by $k^i$.

The first line contains the number of test cases $T$. ($1 \le T \le 100$)

Each of the next $T$ lines contains two integers $n$ and $k$ separated by a space. ($2 \le n \le 10^{18}$, $2 \le k \le 10^{12}$)

For each test case, print the largest $i$ satisfying the condition on its own line.