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 prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

num = int(input())
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41]
k = prime_factors(num)
k.reverse()
c = 1
for i in range(len(k)):
    c *= primes[0]**(k[i]-1)
    primes[0] = primes[0]**(k[i])
    primes.sort()
print(c)
    
    

