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
pri=[2,3,5,7,11,13,17,19,23,29]
def deal(x,y):
    if x==1:
        tmp=1
    else:
        tmp=10**18
    for csx in range(2,x+1):
        if 0==x%csx :
            tmp=min(tmp,pri[y]**(csx-1)*deal(x/csx,y+1))
    return tmp;
print(deal(input(),0))