OPC5 - Auris Love


Little Aurilio likes a cute girl in his class. So one day he approaches her and asks her if he can sit with her in class. Now, the cute girl is very fond of mathematics. So she gives a task. The task is as follows -

You are given two integers n and k. compute maximum l for which (fact(n)%pow(k,l))==0 where fact(n) is factorial n and pow(k,l) is k^l. Help Little Aurilio in impressing the cute little girl. 

INPUT
First line contains number of test cases T next T lines contains two integers n and k. 

OUTPUT
output T separate lines each containing Maximum l for which (n!%pow(k,l))==0. 

CONSTRAINTS
T<=10^3
2<=n,k<=10^9


SAMPLE INPUT
3
2 5
3 3
8 2


SAMPLE OUTPUT
0
1
7


Added by:bashrc is back
Date:2012-03-23
Time limit:0.106s-1s
Source limit:1000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:MNNIT LOCAL OPC

hide comments
2016-07-22 20:46:38 Piyush Kumar
Why the reduced source code limit? What purpose does it serve?
2014-06-13 17:01:01 Anmol Garg
Please increase the source limit for this question. My source size is 917 bytes but still it gives an error when I submit my solution.
2012-03-24 09:12:22 bashrc is back
I have moved the problem to tutorial.The constraints are easier than the original problem.Thanx @alex. But i still maintain the problem was original and its a co-incidence there is a similar problem.
2012-03-24 09:03:35 numerix
I agree with Alex Anderson. Same task already exists, so this one should be removed (at least from classical section).
2012-03-24 09:03:35 Alex Anderson
Right, but the point is that we don't need duplicate problems in the problem set. Found the problem: http://www.spoj.pl/problems/GCPC11A/

Last edit: 2012-03-24 05:06:07
2012-03-24 09:03:35 bashrc is back
@alex anderson The problem is our own problem (including the problem statement and test case data) which we used in our college's local OPC.If there is a similar problem elsewhere then it is merely a co-incidence.
2012-03-24 09:03:35 bashrc is back
@dumps Look at the constraints. "2<=n,k<=10^9"
2012-03-24 09:03:35 dumps
what if k=1,will L be infinity then?what to output for infinity?
2012-03-24 09:03:35 Alex Anderson
I'm pretty sure this problem already exists somewhere, but I can't find the problem ID.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.