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 n, np;
int prime[100];
long long f[1234][12];
long long power(int x, int n) {
  if (n == 0) return 1;
  long long tmp = power(x, n / 2);
  tmp = tmp * tmp;
  if (n % 2) tmp *= x;
  return tmp;
}
int main() {
  scanf("%d", &n);
  for (int i = 2; i < 100; i++) {
    bool status = true;
    for (int j = 2; j < i; j++)
      if (i % j == 0) {
        status = false;
        break;
      }
    if (status) prime[++np] = i;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= 10; j++) f[i][j] = INF;
  f[1][0] = 1;
  for (int i = 2; i <= n; i++)
    for (int j = 1; j <= 10; j++)
      for (int k = 1; k < i; k++)
        if (i % k == 0 && f[k][j - 1] != INF &&
            log10(INF / f[k][j - 1]) / log10(prime[j]) >= (i / k - 1))
          f[i][j] = min(f[i][j], f[k][j - 1] * power(prime[j], i / k - 1));
  long long res = INF;
  for (int i = 0; i <= 10; i++) res = min(res, f[n][i]);
  printf("%I64d", res);
}
