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;
const long long maxn = 5000, inf = 2e18 + 1, mod = 1e9 + 7;
long long n, first[700][100], ans = 4e18;
vector<int> v;
bool used[maxn];
int ln(long long g) {
  int res = 0;
  while (g != 0) g /= 10, res++;
  return res;
}
void rec(int cur, int last, int len, long long val) {
  if (cur == 1) {
    ans = min(val, ans);
    return;
  }
  for (int i = last; i > 1; i--) {
    if (cur % i == 0) {
      if (first[len][i - 1] != 0 && ln(val) + ln(first[len][i - 1]) <= 19 &&
          val * first[len][i - 1] <= inf)
        rec(cur / i, i, len + 1, val * first[len][i - 1]);
    }
  }
}
int main() {
  for (int i = 2; i < maxn; i++) {
    if (!used[i]) {
      v.push_back(i);
      for (int j = i; j < maxn; j += i) used[j] = 1;
    }
  }
  for (int i = 0; i < v.size(); i++) {
    first[i][0] = 1;
    for (int j = 1; j < 100; j++) {
      first[i][j] = first[i][j - 1] * v[i];
      if (ln(v[i]) + ln(first[i][j]) <= 18 && first[i][j] > inf)
        first[i][j] = 0;
    }
  }
  cin >> n;
  rec(n, 99, 0, 1);
  cout << ans;
}
