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
2017-05-03 00:08:12
Reminder to C++ users: __int128 is now a thing :)
2016-01-13 07:08:15 [Rampage] Blue.Mary
PIKE is so slow while processing input/output data...

=(Francky)=> I have a PIKE AC in 2.15s, with the same IO, and almost the same code as yours... I don't think the IO is so slow for PIKE here. But it's true that fast solutions have fast output methods.

Last edit: 2016-01-13 08:07:25
2015-07-23 23:42:07 varun bumb
Finally AC!! really nice problem :)

=(Francky)=> Thanks for your appreciation.

Last edit: 2015-07-24 12:27:31
2015-07-17 20:41:48 Sayak Haldar
Got a wrong answer...then understand that answer would not fit a 64 bit container..this problem is a little difficult for c and c++ users I guess

Last edit: 2015-07-17 20:45:47
2015-07-10 13:38:46 Rishav Goyal
stupid solution. so much float on shit.
2015-06-29 14:27:22 sameer Hussain
Thanks Francky :),
2015-06-27 13:16:25 sameer Hussain
@francky, I am getting WA many a times,
Please Help me ,

=(Francky)=> You have an overflow issue, the answer may not fit in a 64bit container...

Last edit: 2015-06-27 22:34:31
2015-06-26 08:35:50 scyth3r
piece of cake...just i needed was patience :p
Good question@Francky
2015-06-25 20:50:55 :.Mohib.:
AC after lot of WA.... :)
Great one!!

Last edit: 2015-06-25 21:58:16
2015-03-12 04:10:50 Curiosa
@Francky I am getting WA, but I think I am on the right track and cannot find out my mistake.
Are these answers correct?
****
****

(Francky) => No other test case is provided. You have approx. 50% of WA, good luck.

AC, stupid mistake

Last edit: 2015-03-17 18:02:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.