SPOJ.com - Problem FACTMULN

FACTMULN - Product of factorials (easy)

no tags

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

Let G(n) = {i in [1..n], such that n divides F(i)}.

It is obvious that n belongs to G(n) that makes it a non empty set.

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 an integer n.

Output

For each test case, you have to print min(G(n)).

Example

Input:
3
4
5
6

Output:
3
5
3

Explanation

For test case #1:
F(1) = 1! = 1 , not divisible by 4
F(2) = 1! × 2! = 2 , not divisible by 4
F(3) = 1! × 2! × 3! = 12 , divisible by 4
F(4) = 1! × 2! × 3! × 4! = 288 , divisible by 4
So G(4) = {3, 4}.

Constraints

0 < T < 10^4
0 < n < 10^9

A little kB of Python code can get AC in half the time limit. (Edit 2017-02-11, after the compiler changes.)
Input is not randomly chosen ;-) Have fun.

Submit solution!

hide comments

< Previous 1 2 3 Next >

	adhikari vushesh babu: 2014-06-08 21:16:47 @Francky - Can u give me a test case for which my code fails? Submission ID - 11725736 --(Francky)--> OK for 1, but WA for 2, and (almost?) all other cases. Last edit: 2014-06-08 21:49:34
	Samar Holkar: 2014-06-04 20:18:48 My code is getting TLE...please help.My submission id is 11704495 --ans(Francky)--> Your code is a pure brute force one, so it is TLE ; you have to improve your method. It's good to start with such a brute force program, now you have to find a better way. Last edit: 2014-06-04 20:41:55
	Sam Winchester: 2014-05-27 22:56:59 @Francky Can you pls tell me your email id .... I'm facing many problems and want some of your guidance ... --ans(Francky)--> You can post message in forum, I will probably not answer at 100% (busy and not able on many subjects), but you can try. Other people could answer, or only read... I prefer public help/guidance. Thanks for your comprehension. Last edit: 2014-05-27 23:07:10
	[themighty] deathsurgeon: 2014-05-22 16:28:59 Finally!!! The green light! The test cases are really strong!
	Sam Winchester: 2014-05-17 19:53:19 Francky can u pls tell that how someone becomes a problem setter ... Pls its important for me to know ... thanks in advance ... --ans(Francky)--> Congrats for all your solved problems. It seems you're new here, so you should take a bit of time before ask for many changes for old problems. What about if every newcomer ask for tons of changes ? It will a pleasure to add you as psetter, as indicated in tutorials for psetter. Try to solve a substantial amount of decent problems before ask to. Good luck. Thanks a lot sir !! :) Last edit: 2014-05-22 17:52:04
	RIVU DAS: 2014-05-17 10:12:34 @Francky - Can u give me a test case for which my code fails??? I getting WA!!! Submission ID - 11594361 --ans(Francky)--> Now it's only for tricky cases you are wrong. You have to find them. Good luck. @Francky - I checked using brute force and then made a couple of changes, but still WA! ID - 11594949 --ans(Francky)--> I can't give you the tricky cases. Search what could they be ; it's part of the problem. One can't spoil. Last edit: 2014-05-17 22:37:18
	pandu ranga rao: 2014-03-24 06:30:12 @Francky please check my code and tell me where i'm doing wrong in my code.My submission ID is 11314468. --ans(Francky)--> The logic for the problem is not good, you have only WA. You should try a brute force check for small input. @francky I've also tried brute force still i'm getting WA please tell me where my code getting wrong.Here is my submission ID 11315283. --ans(Francky)--> Now it's only for tricky cases you are wrong. You have to find them. Good luck. Last edit: 2014-03-25 18:14:52
	kancha: 2014-03-17 20:49:16 nice question :D:D

Submit solution!

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