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
def prog():
    prime = [1,2,3,5,7,11,13,17,19,23,29]
    dp = []
    inp = input()
    for i in xrange(1001):
        dp+=[[0]*11]
    for i in xrange(10):
        dp[1][i+1] = 1
    xy = 1
    for i in xrange(1,1001):
        dp[i][1] = xy
        xy <<= 1
    for i in xrange(2,1001):
        for j in xrange(2,11):
            m = dp[i][j-1]
            I =(i>>1) + 1
            for k in xrange(1,I):
                if(i%(k+1)==0):
                    K = k
                    xy = dp[i/(k+1)][j-1]
                    while(K!=0):
                        xy *= prime[j]
                        K-=1
                    m = min(m,xy)
            dp[i][j] = m
    print dp[inp][10]
prog()