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
#!/usr/bin/env python3

n = int(input())

def get_factors(n):
  # Find all prime factors of n, including multiples
  result = []
  factor = 2
  while (n != 1):
    if ((n % factor) == 0):
      n = n // factor
      result.append(factor)
    else:
      factor += 1
  return result

factors = get_factors(n)

# Decide on the power of each prime in the answer
primes = [2,3,5,7,11,13,17,19,23,29]
options = list(reversed(factors))

if (options == [2,2,2]):
  options = [4,2]

answer = 1
for (option, prime) in zip(options, primes):
  answer *= prime**(option-1)

print(answer)