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
#include <bits/stdc++.h>
using namespace std;
long long func(long long a, long long b) {
  if ((2000000000000000000ll / a) < b)
    return 2000000000000000000ll;
  else
    return a * b;
}
long long pwr(long long b, int p) {
  long long ret = 1ll;
  for (int i = 0; i < p; i++) {
    if (func(ret, b) == 2000000000000000000ll) {
      ret = 2000000000000000000ll;
      break;
    }
    ret *= b;
  }
  return ret;
}
vector<int> pr, vec;
long long mem[22][22];
long long dp(int p1, int p2) {
  if (p1 == (int)vec.size()) return 1ll;
  if (mem[p1][p2] != -1) return mem[p1][p2];
  mem[p1][p2] = 2000000000000000000ll;
  for (int i = p1, s = 1; i < (int)vec.size(); i++) {
    s *= vec[i];
    mem[p1][p2] = min(mem[p1][p2], func(pwr(pr[p2], s - 1), dp(i + 1, p2 + 1)));
  }
  return mem[p1][p2];
}
int main() {
  for (int i = 2; (int)pr.size() < 20; i++) {
    bool f = 1;
    for (int j = 2; j < i && f; j++)
      if (!(i % j)) f = 0;
    if (f) pr.push_back(i);
  }
  int n;
  scanf("%d", &n);
  for (int i = 0; pr[i] <= n; i++)
    if (!(n % pr[i])) {
      while (!(n % pr[i])) n /= pr[i], vec.push_back(pr[i]);
    }
  if (n != 1) vec.push_back(n);
  sort(vec.begin(), vec.end(), greater<int>());
  memset(mem, -1, sizeof mem);
  printf("%lld\n", dp(0, 0));
  return 0;
}
