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
maxn = ans = 10**20
n = int(raw_input())
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
f = [ [maxn for i in xrange(11)] for i in xrange(1001) ]

def dp(i, j):
    if j == -1:
        if i == 1:
            return 1
        return maxn
    if f[i][j] != maxn:
        return f[i][j]
    for k in xrange(i):
        if i%(k+1) == 0:
            f[i][j] = min(f[i][j], dp(i/(k+1), j-1)*(p[j]**k));
    return f[i][j]

for i in xrange(10):
    ans = min(ans, dp(n, i))
print ans