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(x):
    for i in range(2,x):
        if(x%i==0):
            return False
    return True
def Solve(i,Cnt):
    if(i==len(L)):
        ans=1
        for j in range(9):
            ans*=P[j]**Cnt[j]
        Min[0]=min(Min[0],ans)
        return
    for j in range(9):
        if(Cnt[j]==0):
            Cnt[j]=L[i]-1
            Solve(i+1,Cnt)
            Cnt[j]=0
            break
        e=Cnt[j]
        t=Cnt[j]+1
        t*=L[i]
        t-=1
        Cnt[j]=t
        Solve(i+1,Cnt)
        Cnt[j]=e
    return
n=int(input())

L=[]

for i in range(2,n+1):
    if(n%i==0 and prime(i)):
        x=n
        while(x%i==0):
            x//=i
            L.append(i)

L.sort(reverse=True)
P=[2,3,5,7,11,13,17,19,23,29,31]
Min=[10**18]
Solve(0,[0,0,0,0,0,0,0,0,0])
print(Min[0])
