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 {
	static int[] x=new int[3001];
	static int[] max=new int[3001];
	static boolean[] isp=new boolean[3001];
	static boolean[] iss=new boolean[3001];
	static int[] p=new int[3000];
	static int ed,ped,nn,aa;
	static long dfs(int n,int i){
		long ans=4000000000000000000L;
		if(n==1)return 1; 
		for(int j=2;j<=n;j++)if(n%j==0){
			long k=dfs(n/j,i+1);
			if(Math.pow(p[i],j-1)*k<ans)ans=(long)Math.pow(p[i],j-1)*k;
		}
		return ans;
	}
	public static void main(String args[]){
		for(int i=2;i<=3000;i++){
			if(!isp[i]){
				for(int j=i+i;j<=3000;j+=i)isp[j]=true;
			}
		}
		ed=0;
		for(int i=2;i<=3000;i++){
			if(!isp[i]){
				ed++;
				p[ed]=i;		
			}
		}
		Scanner jin=new Scanner(System.in);
		int n=jin.nextInt();
		if(n==1)System.out.println(1);
		else System.out.println(dfs(n,1));
	}
}

 	   			 	   	 	  				 	 					