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
global primes
global dp
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
dp = [[-1 for i in range(10)] for i in range(1001)]

def solve(i, j):
    if (j == -1):
        if (i == 1):
            return 1
        return 10 ** 18 + 1

    if (dp[i][j] != -1):
        return dp[i][j]

    best = 10 ** 18 + 1
    for k in range(1, i + 1):
        if (i % k != 0):
            continue

        best = min(best, solve(i / k, j - 1) * (primes[j] ** (k - 1)))

    dp[i][j] = best

    return best

n = int(raw_input())
best = 10 ** 18 + 1

for i in range(10):
    best = min(best, solve(n, i))

print best