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
inf = 1<<64
p = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
ans = inf
linf = int(1e18)
def dfs(x, n, m):
    if n==1:
        global ans
        ans = min(ans, m)
        return
    l,k = 1, p[x]
    while l<n and k<linf:
        if n%(l+1) == 0:
            if m*k > linf:
                break
            dfs(x+1, n//(l+1), m*k)
        l += 1
        k *= p[x]
if __name__ == '__main__':
    n = int(input())
    dfs(1, n, 1)
    print (ans)