SP9117 GCPC11A - 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_.

The first line contains the number of test cases _t_ (_1 ). Each of the following _t_ lines contains the two numbers _n,k_ (_2 , _2 ) separated by one space.___

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