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
dc={}

def slv (n, prime=2):
    if (n == 1):
        return 1
        
    global dc 
    
    for i in range (2, 10000):
        if(i*i>prime):
            continue 
        if(prime%i==0):
            return slv(n,prime+1)
    if ((n, prime) in dc):
        return dc[(n, prime)]
    
    ans = 10**50
    for i in range (2, n+1):
        if (n%i==0):
            ans=min(ans, prime**(i-1) * slv(n//i, prime+1))
    
    dc[(n,prime)]=ans
    return ans
    
n = int(input())
print(slv(n))