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-03-07 10:18:18 nitish rao
AC Finally!

Last edit: 2014-03-07 14:44:17
2014-03-06 15:56:05 Akash Agarwal
@Francky Please check my code my submission id is 11196399. I could not find where is the eror can you just give a little hint
--ans(Francky)--> Your code is correct, there was a n=1004065969 in input, your code didn't handle it. I will clean IO files and rejudge. Edit : Done.

--Thank you so much this was a great problem loved solving it
-ans(Francky)--> Thanks for your appreciation.

Last edit: 2014-03-06 16:13:53
2014-03-06 15:56:05 Akash Agarwal
@Francky My submission Id is 11188236
can you please check my code and tell me what error am i making
--ans(Francky)-->You made some wrong assumptions. There are few tricky cases you didn't saw. Good luck.

Last edit: 2014-03-05 14:39:08
2014-03-06 15:56:05 CrazyCoder
Can someone explain me test case 1
--ans(francky)--> Done in description. ;-)

Last edit: 2014-03-02 12:04:58
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.