# nearly square divisors, revisited

def factors(n): # 2,3,5-wheel
    ws = [1,2,2,4,2,4,2,4,6,2,6]
    w, f, fs = 0, 2, []
    while f*f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f, w = f + ws[w], w+1
        if w == 11: w = 3
    if n < f*f: fs.append(n)
    return fs

def knap(target, xs):
    if xs == []: return 0
    if target < xs[0]:
        return knap(target, xs[1:])
    else:
        return max(xs[0] + knap(target-xs[0],xs[1:]), \
                   knap(target, xs[1:]))

def nsd(n):
    from math import log, exp
    fs = map(log, factors(n)[::-1])
    b = int(round(exp(knap(sum(fs)/2, fs))))
    return n/b, b

print nsd(224403121196654400)