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
import java.util.*;

public class E {

    int n;
    ArrayList<Integer> list;
    ArrayList<Integer> P;
    long E9;
    long E18;

    int mod(int L) {
        if (L % 2 != 0)
            return 1;
        else
            return 0;
    }

    void sieve(int L, int U) {
        P = new ArrayList<Integer>();
        int i, j, d;
        d = U - L + 1; /* from range L to U, we have d=U-L+1 numbers. */
        /* use flag[i] to mark whether (L+i) is a prime number or not. */
        boolean[] flag = new boolean[d];
        for (i = 0; i < d; i++)
            flag[i] = true; /* default: mark all to be true */
        for (i = mod(L); i < d; i += 2)
            flag[i] = false;
        /* sieve by prime factors staring from 3 till sqrt(U) */
        for (i = 3; i <= Math.sqrt(U); i += 2) {
            if (i > L && !flag[i - L])
                continue;
            /*
             * choose the first number to be sieved -- >=L, divisible by i, and
             * not i itself!
             */
            j = L / i * i;
            if (j < L)
                j += i;
            if (j == i)
                j += i; /* if j is a prime number, have to start form next one */
            j -= L; /* change j to the index representing j */
            for (; j < d; j += i)
                flag[j] = false;
        }
        if (L <= 1)
            flag[1 - L] = false;
        if (L <= 2)
            flag[2 - L] = true;
        for (i = 0; i < d; i++)
            if (flag[i]) {
                int num = L + i;
                // System.out.println(num);
                P.add(num);
            }

        // System.out.println(L+i);
        // P.add(L + i);
    }

    void primeFactors(int number) {

        int sqrt = (int) Math.sqrt(number);

        for (int i = 2; i <= sqrt; i++) {

            if (number % i == 0) {

                list.add(i);

                number /= i--;
                sqrt = (int) Math.sqrt(number);
            }

        }
        if (number > 1) {
            list.add(number);
        }
    }

    void init() {

    }

    long pow(int p, int e) {

        if (e == 1)
            return p;
        if (e == 0)
            return 1;
        if (e % 2 == 0) {
            // even
            long v1 = pow(p, e / 2);
            if (v1 > E9)
                return Long.MAX_VALUE;
            return v1 * v1;
        } else {
            // odd
            long v1 = pow(p, e - 1);
            if (v1 > E18 / p)
                return Long.MAX_VALUE;
            return p * v1;
        }

    }

    long dp(int i, int j) {

        // base case
        if (i == 0)
            return Long.MAX_VALUE;
        if (i == 1)
            return 1;

        if (j == P.size())
            return Long.MAX_VALUE;

        long min = Long.MAX_VALUE;
        long part, dp;

        for (int k = 0; k + 1 <= i; k++) {

            part = pow(P.get(j), k);
            if (part == Long.MAX_VALUE)
                continue;
            
            if (i % (k + 1) != 0)
                continue;

            dp = dp(i / (k + 1), j + 1);

            if (dp > E18 / part)
                continue;

            min = Math.min(min, part * dp);
        }
        return min;

    }

    void run() {

        sieve(1, 35);
        E9 = 1000000000;
        E18 = E9 * E9;
        Scanner s = new Scanner(System.in);
        list = new ArrayList<Integer>();
        n = s.nextInt();
        primeFactors(n);
        System.out.println(dp(n, 0));

    }

    public static void main(String[] args) {
        new E().run();
    }
}
