B - Exponential Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

正整数 X が与えられます。 X 以下の最大のべき乗数を求めてください。 ただし、べき乗数とは、ある 1 以上の整数 b と 2 以上の整数 p を使って b^p とかける整数のことを指すこととします。

制約

  • 1 ≤ X ≤ 1000
  • X は整数

入力

入力は以下の形式で標準入力から与えられる。

X

出力

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

入力例 1

10

出力例 1

9

10 以下のべき乗数は 1,4,8,9 の 4 つです。 この内最も大きい 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