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

public class Main {
	public static long[] prime = {2,3,5,7,11,13,17,19,23,29,31,37,39,41,43};
	public static int n;
	public static long res;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while ( sc.hasNextInt() ) {
			n = sc.nextInt();
			res = 1L<<61;
			dfs( 1L , 1 , 0 , 59 ); 
			System.out.println(res);
		}
	}
	public static void dfs( long var , int num , int ord , int limit ) {
		if ( num>n || var<0 ) {
			return;
		} else if ( num==n ) {
			res = Math.min( res , var );
		} else {
			long temp = var;
			for ( int i = 1 ; i<=limit ; ++i ) {
				temp *= prime[ord];
				dfs( temp , num*(i+1) , ord+1 , i );
			}
		}
	}
}