Number With The Given Amount Of Divisors

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

inputFormat

Input

The first line of the input contains integer n (1 ≤ n ≤ 1000).

outputFormat

Output

Output the smallest positive integer with exactly n divisors.

Examples

Input

4

Output

6

Input

6

Output

12

样例

6

12