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 =
    1000ll * 1000ll * 1000ll * 1000ll * 1000ll * 1000ll + 1000ll;
long long dp[1100][12];
long long c[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
int pk = 11;
long long power[11][1100];
int main() {
  int n;
  cin >> n;
  if (n <= 2) {
    cout << n << endl;
    return 0;
  }
  for (int i = 0; i < pk; ++i) {
    power[i][0] = 1;
    long long temp = c[i];
    int j;
    for (j = 1; j < 1010; ++j) {
      long long t = power[i][j - 1] * temp;
      if (t > INF || t < 0) break;
      power[i][j] = t;
    }
    for (; j < 1010; ++j) power[i][j] = -1;
  }
  for (int j = 0; j < pk; ++j) dp[1][j] = 1;
  for (int i = 2; i <= n; i++) dp[i][0] = power[0][i - 1];
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < pk; j++) {
      long long a = INF + 10ll;
      for (int k = 0; k <= 1000; k++) {
        if (k >= i) break;
        if (i % (k + 1) != 0) continue;
        long long t = dp[i / (k + 1)][j - 1];
        if (power[j][k] < 0) continue;
        t *= power[j][k];
        if (t < 0 || t > INF) continue;
        a = min(a, t);
      }
      if (a > INF)
        dp[i][j] = -1;
      else
        dp[i][j] = a;
    }
  }
  cout << dp[n][pk - 1] << endl;
  return 0;
}
