FACTMULO - Product of factorials (again)

no tags 

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.


hide comments
hodobox: 2017-05-03 00:08:12

Reminder to C++ users: __int128 is now a thing :)

[Rampage] Blue.Mary: 2016-01-13 07:08:15

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
varun bumb: 2015-07-23 23:42:07

Finally AC!! really nice problem :)

=(Francky)=> Thanks for your appreciation.

Last edit: 2015-07-24 12:27:31
Sayak Haldar: 2015-07-17 20:41:48

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
Rishav Goyal: 2015-07-10 13:38:46

stupid solution. so much float on shit.

sameer Hussain: 2015-06-29 14:27:22

Thanks Francky :),

sameer Hussain: 2015-06-27 13:16:25

@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
scyth3r: 2015-06-26 08:35:50

piece of cake...just i needed was patience :p
Good question@Francky

:.Mohib.:: 2015-06-25 20:50:55

AC after lot of WA.... :)
Great one!!

Last edit: 2015-06-25 21:58:16
Curiosa: 2015-03-12 04:10:50

@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

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