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.
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 ≤ 10^{18}, 2 ≤ k ≤ 10^{12}) 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).
hide comments
nadstratosfer:
20180225 06:16:58
Watch out when using the spoiler for spoilerization, k appears to slightly exceed 10^12. 

[Lakshman]:
20161029 08:49:23
@amartyadav : writing answer at once or writing answer after each test case will not affect the Judge verdict . 

amartyadav:
20161028 23:17:36
@Adrian. Just one question. Does the program have to print all the outputs at last together? I programmed in a manner where outputs will be given for every test case as soon as the first test case input is given.


ashish22_dwd:
20161009 00:11:44
Finally.. AC 

rainy jain :
20160524 08:32:22
@Adrian can you please give any hint why I'm getting WA id:16979406. Last edit: 20160524 08:33:21 

Rishav Goyal:
20140405 16:27:44
awesome !!


SWOOSH!!!:
20130708 13:10:07
@Adrian, my solution gives the correct output for n=10^18,k=2 and n=10^18,k=10^12 but getting WA!!!...Submission id 9624812 Last edit: 20130708 13:33:59 

uli:
20130411 07:02:58
@Adrian: Can you please give me a clue why 9081770 does return NZEC? 

bashrc is back:
20120422 02:08:40
similar problem with reduced constraints http://www.spoj.pl/problems/OPC5/ 

Adrian Kuegel:
20120326 12:13:37
@Akash: please read the warning, and check each line of your code! I saw it with one short look that you can get overflows! 
Added by:  Adrian Kuegel 
Date:  20110705 
Time limit:  0.511s 
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) 