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
import sys
input=sys.stdin.readline
n=int(input())
y=[2,3,5,7,11,13,17,23,29,31]
def dfs(n,pos):
    v=[1,10**18][n>1]
    for i in range(2,n+1):
        if n%i==0:
            v=min(v,y[pos]**(i-1)*dfs(n//i,pos+1))
    return v
print(dfs(n,0))