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.math.BigInteger;
import java.util.Scanner;


public class Main {
    static final int MAX = 1007;
    static BigInteger []P =
            {BigInteger.ZERO,BigInteger.valueOf(2),BigInteger.valueOf(3),BigInteger.valueOf(5),
                    BigInteger.valueOf(7),BigInteger.valueOf(11),BigInteger.valueOf(13),
                    BigInteger.valueOf(17),BigInteger.valueOf(19),BigInteger.valueOf(23),
                    BigInteger.valueOf(29),BigInteger.valueOf(31),BigInteger.valueOf(37),
                    BigInteger.valueOf(41),BigInteger.valueOf(43),BigInteger.valueOf(47),
                    BigInteger.valueOf(53),BigInteger.valueOf(59)};
    static BigInteger [][] D = new BigInteger[MAX][MAX];
    static BigInteger [][] M = new BigInteger[MAX][MAX];
    private static boolean [][] Sol = new boolean[MAX][MAX];
    public static void main ( String[] args )
    {
        Scanner in = new Scanner ( System.in );
        int N;
        for ( int i = 1 ; i < 18 ; i++ )
        {
            D[i][0] = BigInteger.ONE;
            for ( int j = 1 ; j < MAX ; j++ )
                D[i][j] = D[i][j-1].multiply( P[i] );
        }
        while ( in.hasNext())
        {
            N = in.nextInt();
            M[0][1] = BigInteger.ONE;
            for ( int i = 0 ; i < MAX ; i++ )
                for ( int j = 0 ; j < MAX ; j++ )
                    Sol[i][j] = false;
            Sol[0][1] = true;
            for ( int i = 1 ; i < 18 ; i++ )
                for ( int j = 1 ; j <= N ; j++ )
                {
                    for ( int k = 1; k <= N ; k++ )
                    {
                        if ( j*k > N ) continue;
                        if ( !Sol[i-1][j]) continue;
                        if (!Sol[i][j*k] || (M[i-1][j].multiply(D[i][k-1])).compareTo(M[i][j*k])< 0 )
                        {
                            M[i][j*k] = M[i-1][j].multiply(D[i][k-1]);
                            Sol[i][j*k] = true;
                        }
                    }
                }
            System.out.println(M[17][N] );
        }
    }
}

  	  	  	 		 			 	 		 		   	 	