p03352 AtCoder Beginner Contest 097 - Exponential_28750
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
x=int(input())
l=[]
for b in range (1,32):
    for i in range (2,10):
        if b**i <=x:
            l.append (b**i)
print(max(l))
10 1 999 20 610 38 159 107 72 136 217 261 011 001 7 689 747 52 83 8 124 34 235 27 197 25 1074 324 186 309 390 126 485 354 250 524 826 639 424 452 870 552 1023 905 989 1298 1357 1746 44 158 167 65 161 110 111 19 101 15 13 16 2 3 6 4 21 5 36 100 17 114 95 102 39 14 11 9 12 18 59 586 75 86 22 146 30 91 116 24 63 154 35 28 60 66 157 67 279 32 62 33 90 26 31
9 1 961 16
 576
 36
 144
 100
 64
 128
 216
 256
 9
 1
 4
 676
 729
 49
 81
 8
 121
 32
 225
 27
 196
 25
 1024
 324
 169
 289
 361
 125
 484
 343
 243
 512
 784
 625
 400
 441
 841
 529
 1000
 900
 961
 1296
 1331
 1728
 36
 144
 144
 64
 144
 100
 100
 16
 100
 9
 9
 16
 1
 1
 4
 4
 16
 4
 36
 100
 16
 100
 81
 100
 36
 9
 9
 9
 9
 16
 49
 576
 64
 81
 16
 144
 27
 81
 100
 16
 49
 144
 32
 27
 49
 64
 144
 64
 256
 32
 49
 32
 81
 25
 27
