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
n = int(input())

primes = [2,3,5,7,11,13,17,19,23,29]

dp = []
dp.append([])

for i in range(1,n+1):
	dp.append([])
	for j in range(10):
		dp[i].append(0)
		if(i==1):
			dp[i][j] = 1
		else:
			dp[i][j] = 2**(i-1)
			if(j==0):
				continue
			for k in range(1,i):
				if(i%(k+1)==0):
					d = dp[i//(k+1)][j-1] * (primes[j]**k)
					dp[i][j] = min(dp[i][j],d)
			dp[i][j] = min(dp[i][j],dp[i][j-1])
print(dp[n][9])