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 math 
def POW(x, n):
    if n == 0:
        return 1
    if n % 2:
        return POW(x, n - 1) * x
    res = POW(x, n / 2)
    return res * res;

def rec(n, k):
    ans = POW(p[k], n - 1);
    for i in range(2, n + 1):
        if n % i == 0:
            ans = min(ans, rec(n // i, k + 1) * POW(p[k], i - 1))
    return ans
p = []
n = int(input())
for i in range(2, 1001):
    k = int(math.sqrt(i))
    for j in range(2, k + 1):
        if i % j == 0:
            break
    else:
        p.append(i)
print(rec(n, 0))



