Faculty Dividing Powers#6543
Fred Faculty and Paul Power love big numbers. Day after day Fred chooses a random integer and he computes . His friend Paul amuses himself by computing several powers of his randomly chosen integer 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 while Paul chooses a random integer . They want Dave to find the biggest integer such that k^i divides 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 find that integer .
The first line contains the number of test cases t~(1 \le t \le 100). Each of the following lines contain two numbers and k~(2 \le n \le 10^{18}, 2 \le k \le 10^{12}).
For each test case, print the maximum integer on a separate line.
Example 1