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 int N = 2e4 + 100;
const long long int inf = 1e18;
const long long int mod = 998244353;
const int lg = 30;
bool mark[N];
vector<int> p, d[N];
long long int dp[N][100];
long long int pw(long long int x, long long int n) {
  long long int res = 1;
  for (int i = 0; i < n; i++) {
    res *= x;
    res = min(res, inf);
    if (res < 0 || res >= inf) return inf;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for (int i = 2; i < N; i++) {
    if (!mark[i]) p.push_back(i);
    for (int j = 2 * i; j < N; j += i) {
      mark[j] = 1;
      d[j].push_back(i);
    }
  }
  int n;
  cin >> n;
  long long int ans = inf;
  for (int i = 1; i <= n; i++) {
    dp[i][0] = 1;
    dp[i][1] = pw(2, i - 1);
    if (i == n) ans = dp[i][1];
    for (int j = 2; j <= 10; j++) {
      dp[i][j] = inf;
      for (auto x : d[i]) {
        if (dp[i / x][j - 1] >= inf || pw(p[j - 1], x - 1) >= inf ||
            dp[i / x][j - 1] * pw(p[j - 1], x - 1) < 0)
          continue;
        dp[i][j] =
            min(dp[i][j], min(inf, dp[i / x][j - 1] * pw(p[j - 1], x - 1)));
      }
      if (i == n) ans = min(ans, dp[i][j]);
    }
  }
  cout << ans << endl;
  return 0;
}
