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 dd[1005], n;
vector<long long> ngto, res;
long long ans;
long long tinh(long long a, long long n) {
  if (n == 0) return 1;
  if (n == 1) return a;
  long long tmp = tinh(a, n >> 1);
  tmp = tmp * tmp;
  if (n & 1) tmp = tmp * a;
  return tmp;
}
long long f[1005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 2; i * i < 1005; ++i)
    if (!dd[i]) {
      for (int j = i * i; j < 1005; j += i) dd[j] = 1;
    }
  for (int i = 1; i <= 1005; ++i) f[i] = 1e18;
  for (int i = 2; i < 1005 && ngto.size() <= 10; ++i)
    if (!dd[i]) ngto.push_back(i);
  f[1] = 1;
  for (int i = 0; i < ngto.size(); ++i) {
    long long x = ngto[i];
    for (int j = n - 1; j >= 1; --j) {
      long long d = 1;
      long long k = x;
      while (f[j] * k > 0 && j * (d + 1) <= n) {
        f[j * (d + 1)] = min(f[j * (d + 1)], 1ll * f[j] * k);
        k *= x;
        ++d;
      }
    }
  }
  cout << f[n];
}
