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 ≥ 2. For instance, some non-trivial powers are 243 = 3⁵, 400 = 2⁴ 5² = (2² 5¹)², 216000 = 2⁶ 3³ 5³ = (2² 3¹ 5¹)³, and 1866240000 = 2¹² 3⁶ 5⁴ = (2⁶ 3³ 5²)². By contrast, 3, 200 = 2³ 5², and 432000 = 2⁷ 3³ 5³ are not non-trivial powers.

Input

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

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.