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$. \InputFile 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})$. \OutputFile For each test case, print the maximum integer $i$ on a separate line.