You are given a positive integer X. Find the largest perfect power that is at most X. Here, a perfect power is an integer that can be represented as b^p, where b is an integer not less than 1 and p is an integer not less than 2.

Constraints

* 1 ≤ X ≤ 1000
* X is an integer.

Input

Input is given from Standard Input in the following format:


X


Output

Print the largest perfect power that is at most X.

Examples

Input

10


Output

9


Input

1


Output

1


Input

999


Output

961
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int X = sc.nextInt();

        System.out.println(solve(X));

        sc.close();
    }

    static int solve(int X) {
        int result = 1;
        for (int b = 2; b * b <= X; ++b) {
            int power = b * b;
            while (power * b <= X) {
                power *= b;
            }

            result = Math.max(result, power);
        }

        return result;
    }
}