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
p = [2, 3, 5, 7, 11, 13, 17, 23, 29, 31]
b = int(input())
N = [[1]*11 for i in range(b+1)]
for j in range(10):
    N[1][j] = 1
for i in range(2, b+1):
    for j in range(1, 11):
        m = None
        for k in range(i):
            f = i%(k+1)
            if f == 0:
                if j>1:
                    t = N[i//(k+1)][j-1] * p[j-1]**k
                else:
                    t = p[j-1]**(i-1)
                if m is None or t < m:
                    m = t
        N[i][j] = m
print(N[b][10])
