from math import inf, ceil, gcd
from time import clock
from itertools import groupby, accumulate
from operator import mul
from random import randrange

def isqrt(n):
    if n < 0:
        raise ValueError("x must be non-negative")
    if n == 0:
        return 0
    x = 2 ** ((n.bit_length() - 1) // 2 + 1)    # x > sqrt(n)
    y = x - 1
    while y < x:
        x = y
        y = (x + n//x) // 2
    return x

def iroot(k, n):
    'ínt kth root - uses Newton'
    if k == 2:
        return isqrt(n)
    if n < 0:
        if k % 2:
            return -iroot(k, -n)
        else:
            raise ValueError("n must be non-negative")
    if k < 0:
        raise ValueError("k must be non-negative")
    if n in (0, 1):
        return n
    km1 = k-1
    s = 2 ** ((n.bit_length() - 1)//k + 1)
    u = s - 1
    while u < s:
        s = u
        u = (km1*s + n // s**km1) // k
    return s

_small_primes = set((2, 3, 5, 7, 11, 13, 17, 19, 23))

def is_prime(n, k=25):
    """ Miller-Rabin
        returns: True if n is probably prime
                    False if n is composite
        k: number of random trial used
    """
    n = abs(n)
    if n < 29:
        return n in _small_primes
    for pi in _small_primes:
        if not n % pi:
            return False
    if pow(2, n-1, n) != 1:
        return False
    d, s = n - 1, 0
    while not d % 2:
        d //= 2
        s += 1

    def is_spsp(n, a):
        t = pow(a, d, n)
        if t in (1, n-1):
            return True
        for _ in range(s-1):
            t = (t * t) % n
            if t == n - 1:
                return True
            if t == 1:
                return False
        return False
    return all(is_spsp(n, randrange(2, n-1)) for _ in range(k))

def pollard_rho(n, c=3):
    t, h, d = 2, 2, 1
    while d == 1:
        t = (t * t + c) % n
        h = (h * h + c) % n
        h = (h * h + c) % n
        d = gcd(t - h, n)
    if d == n:  # cycle detected
        return pollard_rho(n, c + 1)
    return d

def rho_factors(n):
    if n < 2:
        return [-1] + rho_factors(-n) if n < 0 else []
    fs = []
    while not n % 2:
        n //= 2
        fs.append(2)
    while not (is_prime(n) or n == 1):
        f = pollard_rho(n)
        flist = [f] if is_prime(f) else rho_factors(f)
        for f in flist:
            while not n % f:
                n //= f
                fs.append(f)
    if n > 1:
        fs.append(n)
    return sorted(fs)

def divisors_from_factors(factors):
    """FAST - list of all divisors from factors"""
    fact = [(1,) + tuple(accumulate(g, mul)) for _, g in groupby(factors)]
    div = [1]
    for g in fact:
        div = [d * f for d in div for f in g]
    return div

def divisors(n, factor_gen=rho_factors):
    """FAST - list of all divisors of n"""
    return divisors_from_factors(factor_gen(n))

def bf(n):
    """i <= j <= p"""
    tmin = inf
    fmin = None
    n3 = ceil(n ** (1/3)) + 1
    for i in range(1, n3):
        if n % i == 0:
            m = n // i
            m2 = ceil(m ** (1/2)) + 1
            for j in range(i, m2):
                if m % j == 0:
                    p = m // j
                    s = i + j + p
                    if s < tmin:
                        tmin = s
                        fmin = i, j, p
    return fmin, tmin

def threeway(n):
    divs = sorted(divisors(n), reverse=True)
    n3 = iroot(3, n)
    min_val, min_sol = inf, None
    for x in divs:
        if x > n3:
            continue
        m = n // x
        sqrtm = isqrt(m)
        if x + sqrtm + m // sqrtm >= min_val:
            break
        for y in divs:
            if y < x:
                break
            if y > sqrtm:
                continue
            if m % y == 0:
                z = m // y
                if x + y + z < min_val:
                    min_sol, min_val = (x, y, z), x + y + z
                break
    return min_sol, min_val
        
N = 1890
print(N)
print(threeway(N))
M = 10**40
N = randrange(M, 2*M)
print(N)
print(threeway(N))

if False:
    for n in range(100000+1, 200000+1):
        if n % 1000 == 0:
            print("n=", n)
        f1, s1 = bf(n)
        f3, s3 = threeway(n)
        assert s1 == s3, "{} {} {} {} {} {}".format(n, s1, s3, facs, f1, f3)

    print("Test OK")

if False:
    N1 = 10**12
    N2 = N1 + 1

    t0 = clock()
    for n in range(N1, N2):
        f1, s1 = threeway(n)
    print(clock() - t0)

    t0 = clock()
    for n in range(N1, N2):
        f1, s1 = bf(n)
    print(clock() - t0)