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 dp[1001][11];
int pr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
long long tope = (1LL << 62);
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= 10; j++) {
      long long mini = tope;
      if (i == 1) {
        dp[i][j] = 1;
        continue;
      }
      if (j == 0) {
        dp[i][j] = mini;
        continue;
      }
      long long cur = pr[j - 1];
      for (int k = 1; k < i; k++) {
        if (i % (k + 1) == 0) {
          if (log((long double)dp[i / (k + 1)][j - 1]) + log((long double)cur) <
              log((long double)tope)) {
            mini = min(mini, dp[i / (k + 1)][j - 1] * cur);
          }
        }
        if (log((long double)cur) + log((long double)pr[j - 1]) >
            log((long double)tope))
          break;
        cur = cur * pr[j - 1];
      }
      dp[i][j] = mini;
    }
  }
  long long ans = (1LL << 60);
  for (int i = 1; i <= 10; i++) {
    ans = min(dp[n][i], ans);
  }
  cout << ans << '\n';
}
