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

public class Main {
    static BigInteger[][] f = new BigInteger[11][1010];
    static int[] num  = {0,2,3,5,7,11,13,17,19,23,29};
    static int n;
    static Scanner cin = new Scanner(System.in);
    public static void main(String[] args) {
        for(int i=1;i<=1000;i++)
            f[1][i] = BigInteger.valueOf(num[1]).pow(i-1);
        for(int i=2;i<=10;i++){
            for(int j=1;j<=1000;j++){
                f[i][j] = f[i-1][j];
                for(int k=1;k<j;k++)if( j%(k+1)==0 ){
                     BigInteger test = BigInteger.valueOf(num[i]).pow(k).multiply(f[i-1][j/(k+1)]);
                     if(test.compareTo(f[i][j]) < 0)
                         f[i][j] = test;
                }
            }
        }
        while(cin.hasNext()){
            n = cin.nextInt();
            System.out.println(f[10][n]);
        }
    }
}
