#64Medium

Is it prime

Time: 1 s · Memory: 256 MB

Working with numbers

Statement

You are given a natural number $n$ . Is it prime? A prime is a number greater than $1$ divisible only by $1$ and by itself.

Input format

A single integer $n$ ( $1 \le n \le 10^{12}$ ).

Output format

YES if it is prime, NO otherwise.

Examples

Input

Output

YES

Input

Output

NO

Note

It is enough to search for divisors up to $\sqrt{n}$ (d * d <= n): for $n = 10^{12}$ that is $10^6$ steps, while going up to $n$ would take $10^{12}$ — too slow.

$1$ is not prime. In the second example $91 = 7 \cdot 13$ . Numbers up to $10^{12}$ need long long / int64 — and d * d must be computed in that type as well.

Is it prime

Time: 1 s · Memory: 256 MB

Working with numbers

Statement

You are given a natural number $n$ . Is it prime? A prime is a number greater than $1$ divisible only by $1$ and by itself.

Input format

A single integer $n$ ( $1 \le n \le 10^{12}$ ).

Output format

YES if it is prime, NO otherwise.

Examples

Input

Output

YES

Input

Output

NO

Note

It is enough to search for divisors up to $\sqrt{n}$ (d * d <= n): for $n = 10^{12}$ that is $10^6$ steps, while going up to $n$ would take $10^{12}$ — too slow.

$1$ is not prime. In the second example $91 = 7 \cdot 13$ . Numbers up to $10^{12}$ need long long / int64 — and d * d must be computed in that type as well.