Given the number n, find the smallest positive integer which has exactly n divisors. It is guaranteed that for the given n the answer will not exceed 1018.

Input

The first line of the input contains integer n (1 ≤ n ≤ 1000).

Output

Output the smallest positive integer with exactly n divisors.

Examples

Input

4


Output

6


Input

6


Output

12
def isPrime(i) -> bool:
    t = 2
    while t * t <= i:
        if i % t == 0:
            return False
        t += 1
    return i > 1

MAX_ANS = 10 ** 18
d = int(input())
bound = 25
p = [-1]
for i in range(100000):
    if(isPrime(i)):
        p.append(i)
        if len(p) > bound:
            break

dp = [[MAX_ANS + 1]*(1 + bound) for _ in range(1 + d)]
for i in range(1 + bound):
    dp[1][i] = 1

for i in range(2, 1 + d):
    for k in range(1, 1 + bound):
        dp[i][k] = dp[1][k - 1] * p[k]**(i - 1)
    t = 2
    while t * t <= i:
        if i % t == 0:
            for k in range(1, 1 + bound):
                dp[i][k] = min(dp[i][k], dp[i//t][k - 1] * p[k]**(t - 1), dp[t][k - 1] * p[k]**(i//t - 1))
        t += 1
print(min(dp[d]))
       




