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 sys
x = int(raw_input())
# a = [int(raw_input()) for i in xrange(n)]
# a,b,c,d = map(int, raw_input().split())

p = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

def isPowerOfTwo(n):
    return (n > 0) and (n & (n - 1) == 0)

# s = raw_input()
# k = int(raw_input())


# print "".join(["a","b"])

# print "Yes" if 3 > 0 else "No"
if x < 4:
    print 1
    sys.exit()

X = x

while x > 1:
    n = x

    if isPowerOfTwo(x) == True:
        print x
        sys.exit()
    if x == 2 or x in p:
        x-=1
        continue
    for i in xrange(3,X):
        n = x
        c = 0
        while True:
            if n % i != 0:
                break
            n /= i
            c += 1
            if n == 1 and c > 1:
                print x
                sys.exit()
    x-=1
print 1