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
import java.util.*;

public class Main {

  public static void main(String args[]) {
    Main m = new Main();
    m.exec();
  }

  Scanner cin;
  Main() {
    cin = new Scanner(System.in);
  }

  void exec() {

    int n = cin.nextInt();

    int prime[] = new int[1000];
    int p = 0;
    prime[p++] = 2;
  MAIN:
    for(int i=3; i<=2000; i+=2) {
      for(int j=0; j<p; ++j) {
        if( i % prime[j] == 0 ) { continue MAIN; }
      }
      prime[p++] = i;
    }

    long cur = 1;
    long ans = 1000000000000000000L;

    System.out.println(solve(cur, ans, 0, 62, n, prime));

  }

  long solve(long cur, long ans, int pindex, int begin, int rest, int prime[]) {
    if( rest == 1 ) { return Math.min(cur, ans); }
    long thres = (ans / cur);
  SUB:
    for(int j=begin; j>=2; --j) {
      if( rest % j != 0 ) { continue; }
      long me = 1L;
      for(int k=1; k<j; ++k) {
        me *= prime[pindex];
        if( me > thres ) { continue SUB; }
      }
      ans = Math.min(ans, solve(cur * me, ans, pindex + 1, j, rest / j, prime));
    }
    return ans;
  }

}
