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 factorize(n):
    m = n
    i = 2
    v = []

    while(i * i <= m):
        while(n % i == 0):
            v.append(i)
            n /= i
        i += 1

    if (n != 1):
        v.append(n)

    return v

if __name__ == "__main__":
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
    n = int(raw_input())
    v = factorize(n)
    v.sort(reverse = True)

    m = len(v)
    ans = 10 ** 18 + 1
    for i in range(0, 1 << m):
        b = []
        temp = 1
        
        for j in range(m):
            if (i & (1 << j)):
                temp *= v[j]
            else:
                b.append(v[j])

        b.append(temp)
        b.sort(reverse = True)

        x = 1
        for j in range(len(b)):
            x *= primes[j] ** (b[j] - 1)

        ans = min(ans, x)

    print ans