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;
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int n;
  cin >> n;
  long long int inf = 1e18;
  long long int dp[1005][15];
  for (long long int i = 0; i < 1005; i++)
    for (long long int j = 0; j < 15; j++) dp[i][j] = inf;
  dp[1][0] = 1;
  dp[2][1] = 2;
  long long int res[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
  for (long long int i = 3; i <= n; i++) {
    for (long long int j = 1; j < 11; j++) {
      for (long long int k = 1; i / (k + 1); k++) {
        if (i % (k + 1) == 0) {
          if (dp[i / (k + 1)][j - 1] != inf &&
              dp[i / (k + 1)][j - 1] <
                  (long double)(1.0 * dp[i][j] / (long long)pow(res[j - 1], k)))
            dp[i][j] = min(dp[i][j], dp[i / (k + 1)][j - 1] *
                                         (long long)pow(res[j - 1], k));
        }
      }
    }
  }
  long long int min1 = inf;
  for (long long int i = 0; i < 11; i++) min1 = min(min1, dp[n][i]);
  cout << min1 << endl;
  return 0;
}
