SPOJ.com - Problem FACTMULO

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.

Submit solution!

hide comments

< Previous 1 2 Next >

	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**

Submit solution!

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