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 >

	devil: 2015-01-02 22:52:27 @Francky-thnx a ton..!!!, ur last tip did the trick..... :)
	devil: 2015-01-02 21:13:30 @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
	black MaMbA: 2014-08-19 04:15:35 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
	fitcat: 2014-04-08 07:05:06 Nice problem. Enjoyed solving it. --ans(Francky)--> Thanks for your appreciation. Last edit: 2014-04-08 07:30:32
	aqfaridi: 2014-03-14 05:55:20 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
	aqfaridi: 2014-03-13 17:41:13 @francky my code complexity is O(64testcases) 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*
	nitish rao: 2014-03-08 05:15:55 @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

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