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 k2, k3 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 ki 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 ≤ t ≤ 100). Each of the following t lines contains the two numbers n,k (2 ≤ n ≤ 1018, 2 ≤ k ≤ 1012) separated by one space.

Output

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

Example

Input:
2
5 2
10 10

Output:
3
2

Be careful with overflows in this problem (use 64 bit integers, avoid multiplications which will lead to overflow).


Added by:Adrian Kuegel
Date:2011-07-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Authors: Christopher Dennl and Thomas Fersch)

hide comments
2011-07-12 13:01:34 Akshay Kulkarni
@Adrian Can You Please check my code with submission id :- 5357186. Its working on all the test cases including the one mentioned here but giving WA on Judge
Thanks
2011-07-12 13:01:34 Adrian Kuegel
for n=10^18 and k=2 the answer is 999999999999999976, and for n=10^18 and k=10^12 answer is 20833333333333332.
2011-07-12 13:01:34 Problem Solver
What's answer for n=10^18 and k=2
816421509021893143?
and for max test : n=10^18 and k=10^12
20133546667212800?
Thanks for any hint
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.