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
## KALAM
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
n = int(input())
dp = []
for i in range(n + 1):
    t = []
    for j in range(len(p)):
        t.append(0)
    dp.append(t)

for i in range(10):
    dp[1][i] = 1
for i in range(2 , n + 1):
    dp[i][0] = p[0] ** (i - 1)
    for j in range(1 , len(p)):
        dp[i][j] = dp[i][j - 1]
        for k in range(2 , i + 1):
            if(i % k > 0):
                continue
            dp[i][j] = min(dp[i][j] , dp[i // k][j - 1] * (p[j] ** (k - 1)))
A = dp[n][0]
for i in range(len(p)):
    A = min(A , dp[n][i])
print(A)
