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
p=[2,3,5,7,11,13,17,19,23,29,31,37,41,43]
def go(n,i):
  v=(1,10**18)[n>1]
  for d in range(2,n+1):
    if 0==n%d:
      v=min(v,p[i]**(d-1)*go(n/d,i+1))
  return v
print go(input(),0)
