PON - Prime or Not

Given the number, you are to answer the question: "Is it prime?"

Solutions to this problem can be submitted in C, C++, Pascal, Perl, Python, Ruby, Lisp, Hask, Ocaml, Prolog, Whitespace, Brainf**k and Intercal only.

Input

t – the number of test cases, then t test cases follows. [t <= 500]
Each line contains one integer: N [2 <= N <= 2^63-1]

Output

For each test case output string "YES" if given number is prime and "NO" otherwise.

Example

Input:
5
2
3
4
5
6

Output:
YES
YES
NO
YES
NO

Added by:Roman Sol
Date:2005-01-24
Time limit:21s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 BASH CSHARP CLPS D ERL FORTRAN ICON JAVA JS-RHINO LUA NEM NICE PHP PIKE ST
Resource:ZCon 2005

hide comments
2012-12-06 08:02:36 jkp
my program is working in ideone.com but it gives TLE...........why???????
2013-02-24 22:39:57 !!***Still-Fattu***!!
GADIYA THA......
2012-09-20 14:52:30 Atul Kumar Verma
i am getting wrong answer. my program is fairly working in all cases. any special cases to check?
2012-08-25 21:03:47 Alexander Shlemov
Please, make test more strong!!! For example, add several Carmichel numbers. It's bad, when "one Fermat iteration works"
2012-08-15 13:46:18 StupidGuy
Man..finally AC :),
Had to use 2 Iterations with Fermat's.

EDIT: Can be done with single Iteration :)

Last edit: 2012-11-18 12:05:05
2012-07-25 03:31:01 Aditya Pande
good problem but very weak test cases and the time limit is too too high

Last edit: 2012-07-25 03:38:38
2012-06-09 07:20:50 Surya kiran
hariprasanth Never post your code even it is WA..Your code gives YES for 35...check that
2012-06-09 06:11:33 hariprasath
@vit YES for 9223372036854775783??
2012-06-09 06:09:56 hariprasath
@libra not accepting,when NO for 2,3,5
2012-03-25 05:56:37 Darky
Getting TLE even after using Little fermat th. using python! Any help?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.