Is it a power? P51271

Write a program to tell if a natural number $n$ is a non-trivial power, that is, if it can be expressed as $x^m$, where both $x$ and $m$ are natural numbers, and $m \ge 2$. For instance, some non-trivial powers are $243 = 3^5$, $400 = 2^4 5^2 = (2^2 5^1)^2$, $216000 = 2^6 3^3 5^3 = (2^2 3^1 5^1)^3$, and $1866240000 = 2^{12} 3^6 5^4 = (2^6 3^3 5^2)^2$. By contrast, 3, $200 = 2^3 5^2$, and $432000 = 2^7 3^3 5^3$ are not non-trivial powers.

Input

Input consists of several cases, each with a natural number $n$ between 2 and $10^6$.

Output

Print every $n$ followed by “yes” or “no”, depending on whether it is a non-trivial power.

Observation

You should not use the mathematical function @pow()@ nor any alike function to solve this problem.

Hint

A possible solution uses a variant of the sieve of Eratosthenes to precompute a prime factor of each number before starting to read the input.