FACTMULO - Product of factorials (again)

For n positive integer, let F(n) = 1! × 2! × 3! × 4! × ... × n!, product of factorial(i) for i in [1..n],

For p a prime number, and n an integer, and let V(p, n) = max({i>=0 integer, such that p^i divides F(n)}).

Input

The first line of input contains an integer T, the number of test cases.
On each of the next T lines, your are given two integers p a prime number, and n.

Output

For each test case, you have to print V(p, n).

Example

Input:
2
2 3
3 4

Output:
2
2

Constraints

0 < T < 10^5
1 < p < 10^18, a prime number
0 < n < 10^18

p and n are log-uniform independent randomly distributed.

Four lines of Python code can get AC in half the time limit. (Edit 2017-02-11, after compiler changes)
;-) Have fun.


Added by:Francky
Date:2014-03-01
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2015-01-02 22:52:27 devil
@Francky-thnx a ton..!!!, ur last tip did the trick..... :)
2015-01-02 21:13:30 devil
@Francky: i am getting WA, though i think my code is correct....can some one tell me are the following answers correct.....???
--(francky)--> No other test case is provided. Your answers were a bit small compared to correct answer. (the reason is overflow, your container is to small for the answer).
--francky--> tip for Python3 : // is division between integers, / will give you a float. Use //.

Last edit: 2015-01-02 22:46:32
2014-08-19 04:15:35 black MaMbA
A great problem.
Trying to reduce the running time further but cannot do so,could you help me please
--(ans)--> I can't tell you more than try many experiments.
That's okay,just one more thing,can we use psyco module with python 2.7 on spoj

Last edit: 2014-08-22 03:10:01
2014-04-08 07:05:06 fitcat
Nice problem. Enjoyed solving it.
--ans(Francky)--> Thanks for your appreciation.

Last edit: 2014-04-08 07:30:32
2014-03-14 05:55:20 aqfaridi
very nice problem ..learnt a lot from it... got ACed after two days of efforts :)
--ans(francky)--> Thanks for your appreciation.

Last edit: 2014-03-14 08:28:37
2014-03-13 17:41:13 aqfaridi
@francky my code complexity is O(64*testcases) but still i m getting TLE WHY ?? id:11242791
--ans(Francky)--> The complexity is 64/case for the worst case and is from 1 to 64 per case in general. Your method can be simpler, you're not so far. Good luck.

Last edit: 2014-03-14 00:06:40
2014-03-08 05:15:55 nitish rao
@francky I thought my solution was efficient. But getting TLE! Can't figure out why. Please help.
--ans(francky)--> You should first check results, I see only WA. Good luck.

Last edit: 2014-03-08 08:51:02
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.