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
n = int(raw_input())
qs = []
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
res = None

def solve():
    global res
    j = len(qs)-1
    cur = 1
    for i in range(len(qs)):
        cur *= primes[j]**qs[i]
        j -= 1
    if res is None or cur < res:
        res = cur

def rec(n, k):
    if n == 1:
        solve()
    elif k > n:
        return
    else:
        while k <= n:
            if n%k == 0:
                qs.append(k-1)
                rec(n/k, k)
                qs.pop()
            k += 1

rec(n, 2)
print res
