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>
int arr[10]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int n;
long long m = 1e18;
void Solve(long long cur, int div, int p) {
  if (p < 0) {
    if (div == n && m > cur) m = cur;
    return;
  }
  int i = 0;
  long long raised = 1;
  while (true) {
    long long temp = cur * raised;
    if (temp > m) break;
    Solve(temp, div * (i + 1), p - 1);
    ++i;
    raised *= arr[p];
  }
}
int main() {
  std::cin >> n;
  Solve(1, 1, 9);
  std::cout << m << '\n';
  return 0;
}
