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

public class Test5 {

    static HashSet<ArrayList<Integer>> ha = new HashSet<>();

    public static void main(String[] z) {
        int a = new Scanner(System.in).nextInt(), d=2, i=0, h=0, f=0, c=2, u, x=1, v=0, o=0, b=0;
        double r = 1, j=1;
        ArrayList<Integer> l = new ArrayList<>();
        for(; a>1; d+= a%d<1 ? 0 : 1) if(a%d<1) {l.add(d); a/=d; i++;}
        int[] k = new int[i], p = new int[100], ma;
        for(; f<100; c++, x=1){
            for(u=2; u<=Math.sqrt(c); u++) x = c%u<1 ? 0 : x;
            if(x>0){
                p[f]=c;
                f++;
            }
        }
        for(; h<i; h++) k[h]=l.get(i-h-1)-1;
        for(; v<i; v++) r*=Math.pow(p[v], k[v]);
        f(l,r);
        for(ArrayList<Integer> li : ha){
            j=1;
            b=0;
            ma = new int[li.size()];
            for(o=0; o<li.size(); o++) ma[o]=li.get(o);
            Arrays.sort(ma);
            for(; o>0; o--, b++) j*=Math.pow(p[b], ma[o-1]-1);
            r = j<r ? j : r;
        }
        System.out.print(r>Math.pow(10,18)+1 ? 0 : (long)r);
    }

    static void f(ArrayList<Integer> l, double r){
        int d = l.size(), n=0, k=1, q=0;
        ArrayList<Integer> x = l;
        for(; n<d-1; n++){
            for(k = n+1; k<d; k++){
                x = (ArrayList<Integer>)l.clone();
                x.add(l.get(n)*l.get(k));
                x.remove(k);
                x.remove(n);
                q = ha.size();
                ha.add(x);
                if(ha.size()>q) f(x,0);
            }
        }
    }
}
