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.


hide comments
Shark: 2014-08-27 21:49:38

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
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


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