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
n=int(input())

pr=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61]
pprr=set(pr)

dp=[[0 for i in range(9)] for j in range(1005)]

def it(n,pref):
    global dp
    if dp[n][pref]>0:
        return dp[n][pref]
    if n in pprr or pref==0:
        dp[n][pref]=2**(n-1)
        return dp[n][pref]
    dp[n][pref]=it(n,pref-1)
    d=2
    while d*d<=n:
        if n%d==0:
            dd=d
            t=pr[pref]**(dd-1)*it(n//dd,pref-1)
            dp[n][pref]=min(t,dp[n][pref])
            dd=n//d
            t=pr[pref]**(dd-1)*it(n//dd,pref-1)
            dp[n][pref]=min(t,dp[n][pref])
        d+=1
    return dp[n][pref]


print(it(n,8))
    
        
