FACTMULN - Product of factorials (easy)

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.


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

hide comments
2014-06-08 21:16:47 adhikari vushesh babu
@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
2014-06-04 20:18:48 Samar Holkar
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
2014-05-27 22:56:59 Sam Winchester
@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
2014-05-22 16:28:59 [themighty] deathsurgeon
Finally!!! The green light! The test cases are really strong!
2014-05-17 19:53:19 Sam Winchester
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
2014-05-17 10:12:34 RIVU DAS
@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
2014-03-24 06:30:12 pandu ranga rao
@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
2014-03-17 20:49:16 kancha
nice question :D:D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.