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
INF = 20**18
primes = []
a = [1]*100

def crivo():
    for i in range(2, 100):
        if a[i]:
            primes.append(i)
            for j in range(i+i, 100, i):
                a[j] = 0    


def dp(div, idx):
    div = int(div)
    idx = int(idx)

    if div == 1:
        return 1

    resp = INF

    for i in range(1, div):
        if div%(i+1) == 0:
            resp = min(resp, primes[idx]**i * dp(div/(i+1), idx+1))

    return resp
crivo()
n = int(input())

print(dp(n, 0))
 		  	 	   	  		    				  	 			