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

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
dp = [[-1 for i in range(12)] for i in range(1100)]


def solve(divisors, index):
    if (divisors == 1):
        return 1
    if (index == 11):
        return 9999999999999999999999999999
    if dp[divisors][index] != -1:
        return dp[divisors][index]

    ans = 9999999999999999999999999999
    for i in range(1, divisors + 1):
        if (divisors % i == 0):

            temp = solve(divisors // i, index + 1) * (primes[index] ** (i - 1))
            ans = min(ans, temp)

    dp[divisors][index] = ans
    return dp[divisors][index]


n = int(input())
print(solve(n, 0))
