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
2016-12-18 14:50:32 Vipul Srivastava
Lovely question..!!
2015-09-19 10:49:45
soln id:15160697
@Francky it's not a navie solution but it still gives TLE
can you check and tell me if i have to improve on the code?

=(Francky)=> You should use a sieving method, instead of a next_P function, way too slow.

Last edit: 2015-09-21 14:50:11
2015-07-25 23:13:59 varun bumb
Nice problem!
2015-05-26 16:46:47 :.Mohib.:
Finally done...!! Awsm problem....!!
Thnx for the problem Francky sir... :)

Last edit: 2015-06-22 11:10:49
2015-01-15 09:03:12 Soma
@Francky can you please check where my code is giving WA.. my submission ID=13431072
--Francky--> You could check, for example, when you are given a power of 2.


@francky thank you. my solution got accepted.

Last edit: 2015-01-21 15:47:03
2014-12-28 21:06:09 Mayank Poply
@Francky - Can u give me a test case for which my code fails?I am getting WA Submission ID - 13293486
--(francky)--> For an important amount of cases, your program output 13, and it's not the answer. You can solve some small cases, it's true.

Last edit: 2014-12-28 21:13:10
2014-11-22 10:28:27 Francky
@Shanmukh : your assert is wrong, you have always 0 < n < 10^9 in the input file.

Last edit: 2014-11-22 10:29:55
2014-11-22 06:13:48 :(
Range of n is more than 10^9 ... Make your code for entire int range. Got 9 WA's due to unclear range :( . Finally AC :D

Last edit: 2014-11-22 08:53:55
2014-08-28 23:17:19 Sandeep Singh
Finally solve it , there are some corner(difficult) cases :)

Last edit: 2014-08-28 23:18:37
2014-08-27 21:49:38 Shark
submission id : 12248287. @francky plz look thru my code n tell if most of cases are wrong or just some edge cases.

Last edit: 2014-08-27 21:50:12
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.