Faculty Dividing Powers

Fred Faculty and Paul Power love big numbers. Day after day Fred chooses a random integer $n$ and he computes $n!$. His friend Paul amuses himself by computing several powers of his randomly chosen integer $k$ like $k^2$, $k^3$, and so on. On a hot summer day, Fred and Paul got really, really bored, so they decided to play a joke on their buddy Dave Divider. Fred chooses a random integer $n$ while Paul chooses a random integer $k$. They want Dave to find the biggest integer $i$ such that $k^i$ divides $n!$ without a remainder, otherwise they will throw a cake in Dave's face.

Because Dave does not like cakes in his face, he wants you to help him finding that integer $i$.

Input

The first line contains the number of test cases $t(1\le t\le 100)$. Each of the following $t$ lines contains two numbers $n$ and $k(2\le n\le 10^{18},2\le k\le 10^{12})$.

Output

For each test case, print the maximum integer $i$ on a separate line.

Examples