B - Exponential

Time Limit: 2 sec / Memory Limit: 1024 MB

• 1 X 1000
• X は整数

入力

X


出力

X 以下の最大のべき乗数を出力せよ。

入力例 1

10


出力例 1

9


10 以下のべき乗数は 1,4,8,94 つです。 この内最も大きい 9 を出力してください。

入力例 2

1


出力例 2

1


入力例 3

999


出力例 3

961


Score : 200 points

Problem Statement

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.

Sample Input 1

10


Sample Output 1

9


There are four perfect powers that are at most 10: 1, 4, 8 and 9. We should print the largest among them, 9.

Sample Input 2

1


Sample Output 2

1


Sample Input 3

999


Sample Output 3

961