Project Euler #63: Powerful digit counts

_{This problem is a programming version of Problem 63 from projecteuler.net}

The number, , is also a fifth power. Similarly, the 9-digit number, , is a ninth power.

Given , print the positive integers which are also an power?

Input Format

Input contains an integer

Constraints

Output Format

Print the answer corresponding to the test case.

Sample Input

Sample Output