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

public class Codeforces
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int n=Integer.parseInt(bu.readLine()),i=2;
        ArrayList<Integer> al=new ArrayList<>();
        while(al.size()<20)
        {
            if(prime(i)) al.add(i);
            i++;
        }
        System.out.println(mincal(1,n,1,0,al));
    }

    static boolean prime(int n)
    {
        for(int i=2;i*i<=n;i++)
            if(n%i==0) return false;
        return true;
    }

    static long mincal(int d,int n,long cur,int pi,ArrayList<Integer> p)
    {
        if(d==n) return cur;

        long res=(long)1e18;
        for(int pow=1;;pow++) // this loop is O(logN)
        {
            cur*=p.get(pi);
            if(d*(pow+1)>n || cur>res) break;
            res=Math.min(res,mincal(d*(pow+1),n,cur,pi+1,p));
        }
        return res;
    }
}