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 10<sup class="upper-index">18</sup>.
The first line of the input contains integer *n* (1 ≤ *n* ≤ 1000).
import math


def main():
    n = int(input())

    if n == 1:
        print(1)
        return

    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
    prime_factors = []
    i = 2
    while n != 1:
        while not n % i:
            n //= i
            prime_factors.append(i)
        if n == 1:
            break
        i += 1
    prime_factors.reverse()
    while len(prime_factors) > 1:
        sum0 = math.prod([primes[i] ** (prime_factors[i] - 1)for i in range(len(prime_factors))])
        p1 = prime_factors[:]
        p1[0] *= p1[-1]
        p1.pop()
        sum1 = math.prod([primes[i] ** (p1[i] - 1) for i in range(len(p1))])
        p2 = prime_factors[:]
        p2[0] *= p2[-1]
        p2.pop()
        sum2 = math.prod([primes[i] ** (p2[i] - 1) for i in range(len(p1))])
        if min(sum0, sum1, sum2) == sum0:
            print(sum0)
            return
        elif min(sum0, sum1, sum2) == sum1:
            prime_factors = p1[:]
        else:
            prime_factors = p2[:]

    print(2 ** (prime_factors[0] - 1))


if __name__ == "__main__":
    main()
