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
from math import *
from Queue import *


primes = [2,3,5,7,11,13,17,19,23,29]

def small(n,i):
    res = 10**18
    if n == 1:
        return 1
    for j in range(2,n+1):
        if n%j == 0:
            res = min(res, primes[i]**(j-1)*small(n/j,i+1))
    return res

n = int(raw_input())
print(small(n,0))
