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;
vector<int> now;
long long ans = (1LL << 60), p[7] = {2, 3, 5, 7, 11, 13, 17};
void test() {
  long long t = 1;
  int flag = 0;
  for (int i = 0; i < (int)now.size(); i++) {
    for (int j = 1; j < now[i]; j++) {
      t *= p[now.size() - 1 - i];
      if (t >= ans) {
        flag = 1;
        break;
      }
    }
    if (t >= ans) {
      flag = 1;
      break;
    }
  }
  if (flag == 0) ans = t;
}
void go(int n, int L) {
  while (L * L <= n) {
    if (n % L == 0) {
      now.push_back(L);
      go(n / L, L);
      now.pop_back();
    }
    ++L;
  }
  now.push_back(n);
  test();
  now.pop_back();
}
int main(void) {
  int n = 514;
  scanf("%d", &n);
  go(n, 2);
  printf("%I64d\n", ans);
  return 0;
}
