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 INF = (long long)1e18;
int a[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61},
    n, len = 18;
long long dp[10][1 << 10], num[1 << 10], lim[18];
template <class T>
inline T high_bit(T x) {
  return x & (x - 1);
}
inline long long fen(long long x, long long k) {
  long long t = 1, p = x;
  while (k) {
    if (k & 1) t = t * p;
    p = p * p;
    k >>= 1;
  }
  return t;
}
int main() {
  while (scanf("%d", &n) != EOF) {
    if (n == 1) {
      cout << 1 << endl;
      continue;
    }
    vector<int> v;
    for (int i = 0; i < len; i++) {
      while (n % a[i] == 0) n /= a[i], v.push_back(a[i]);
    }
    int m = v.size();
    memset(num, 0, sizeof(num));
    memset(lim, 0, sizeof(lim));
    for (int i = 0; i < len; i++) {
      long long t = 1;
      while (t <= INF / a[i]) t *= a[i], lim[i]++;
    }
    for (int i = 0; i <= m; i++)
      for (int j = 0; j < (1 << m); j++) dp[i][j] = INF;
    dp[0][0] = num[0] = 1;
    for (int i = 0; i < m; i++) num[1 << i] = v[i];
    for (int i = 1; i < (1 << m); i++)
      if (!num[i]) {
        int x = high_bit(i);
        num[i] = num[i - x] * num[x];
      }
    long long ans = INF;
    for (int j = 0; j < m; j++) {
      for (int i = 1; i < (1 << m); i++) {
        for (int k = 0; k < (1 << m); k++)
          if (i == (i | k) && dp[j][k] != -1 && num[i ^ k] <= lim[j]) {
            long long tmp = fen(a[j], num[i ^ k] - 1);
            if (dp[j + 1][i] / tmp > dp[j][k]) dp[j + 1][i] = dp[j][k] * tmp;
          }
      }
      ans = min(ans, dp[j + 1][(1 << m) - 1]);
    }
    cout << ans << endl;
  }
  return 0;
}
