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
def fact(n):
    p = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            p[d-1] = p.get(d-1,0)+1
            n //= d
        d += 1
    if n > 1:
        p[n-1] = p.get(n-1,0) + 1
    return p

def isPrime(n):
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n and n % d != 0:
        d += 2
    return d * d > n

m = int(input())
if not (m & (m - 1)) and m != 1 :
    st = 1
    while m > 2 :
        m //= 2
        st += 1
    if st > 2 :
        res = 24
        kkk = 5
        st -= 3
        while st > 0 :
            res *= kkk
            st -= 1
            kkk += 2
    else :
        res = 2 + 4 * (st-1)
else :
    g = fact(m)
    z = []
    for i,j in g.items():
        z.extend([i]*(j))
    z.sort(reverse=True)
    res = 1
    pros = 2
    for i in z :
        res *= pros**i 
        pros += 1
        while not isPrime(pros) :
            pros += 1
print(res)