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
primes = []
prime_powers = []

calculated = {}


def generate_primes(n=1000):
    global primes

    is_composite = [False] * (n + 1)
    primes = [2, 3]
    
    p = 5
    while p <= n:
        if not is_composite[p]: 
            primes.append(p)
            for i in range(p**2, n + 1, p << 1):
                is_composite[p] = True
                
        p += 2 + ((p + 1) % 3)

        
def generate_prime_powers():
    global primes
    
    limit = 1e18
    
    for p in primes:
        prime_powers.append([])
        m = 1
        while m <= limit:
            prime_powers[-1].append(m)
            m *= p


def solve(n, p):
    global primes, calculated
    
    if (n, p) in calculated:
        return calculated[n, p]
    
    if n == 1:
        calculated[n, p] = 1
        # print (" " * p) + "bam!"
        return 1
        
    answer = float("inf")
    for i in range(1, n / 2 + 1):
        if n % i == 0 and (n / i) <= len(prime_powers[p]):
            # print (" " * p) + "{:}^{:}".format(primes[p], (n / i) - 1)
            answer = min(answer, prime_powers[p][(n / i) - 1] * solve(i, p + 1))
    
    calculated[n, p] = answer   
    return answer
    

n = input()

generate_primes(n)
generate_prime_powers()

print solve(n, 0)
