JATC's math teacher always gives the class some interesting math problems so that they don't get bored. Today the problem is as follows. Given an integer $n$, you can perform the following operations zero or more times:  mul $x$: multiplies $n$ by $x$ (where $x$ is an arbitrary positive integer).  sqrt: replaces $n$ with $\sqrt{n}$ (to apply this operation, $\sqrt{n}$ must be an integer). 

You can perform these operations as many times as you like. What is the minimum value of $n$, that can be achieved and what is the minimum number of operations, to achieve that minimum value?

Apparently, no one in the class knows the answer to this problem, maybe you can help them?


-----Input-----

The only line of the input contains a single integer $n$ ($1 \le n \le 10^6$) — the initial number.


-----Output-----

Print two integers: the minimum integer $n$ that can be achieved using the described operations and the minimum number of operations required.


-----Examples-----
Input
20

Output
10 2
Input
5184

Output
6 4


-----Note-----

In the first example, you can apply the operation mul $5$ to get $100$ and then sqrt to get $10$.

In the second example, you can first apply sqrt to get $72$, then mul $18$ to get $1296$ and finally two more sqrt and you get $6$.

Note, that even if the initial value of $n$ is less or equal $10^6$, it can still become greater than $10^6$ after applying one or more operations.

Difficulty: interview

Starter code:

Solutions:
def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())
MX = 10 ** 5

n = ii()
fac = 2
pr = []
while fac * fac <= n:
    c = 0
    while n % fac == 0:
        c += 1
        n //= fac
    if c:
        pr.append((fac, c))
    fac += 1
if n > 1:
    pr.append((n, 1))
if pr:
    mx = max(e for p, e in pr)
    mn = min(e for p, e in pr)
    mx2 = 1
    cnt = 0
    while mx2 < mx:
        mx2 *= 2
        cnt += 1
    ans = cnt + int(mn != mx2)
    pdt = 1
    for p, e in pr:
        pdt *= p
else:
    pdt, ans = 1, 0
print(pdt, ans)


n = int(input())

if n == 1:
	print('1 0')
else:
	d = 2
	decomp = []
	while d * d <= n:
		cnt = 0
		while n % d == 0:
			cnt += 1
			n //= d
		if cnt > 0:
			decomp += [(d, cnt)]
		if d == 2:
			d += 1
		else:
			d += 2
	if n > 1:
		decomp += [(n, 1)]

	tar = 1
	maxExp = 0
	for e in decomp:
		tar *= e[0]
		maxExp = max(maxExp, e[1])
	
	divCnt = 0
	curExp = 1
	while curExp < maxExp:
		divCnt += 1
		curExp *= 2

	mulRequired = False
	for e in decomp:
		if e[1] != curExp:
			mulRequired = True
			break
	if mulRequired:
		divCnt += 1

	print('%s %s' % (tar, divCnt))



n = int(input())

if n == 1:
    print(1, 0)
    return

factors = {}
mindegree = float("inf")
maxdegree = 0
answer = 1

for x in range(2, int(n ** 0.5) + 1):
    if n == 1: break
    multiplicity = 0
    while n % x == 0:
        n = n // x
        multiplicity += 1
    if multiplicity:
        answer *= x
        #factors[x] = multiplicity
        mindegree = min(mindegree, multiplicity)
        maxdegree = max(maxdegree, multiplicity)

if n != 1:
    #factors[n] = 1
    answer *= n
    mindegree = min(mindegree, 1)
    maxdegree = max(maxdegree, 1)

deg = 0
while 2 ** deg < maxdegree:
    deg += 1

result = deg + 1
if 2 ** deg == maxdegree == mindegree:
    result -= 1
print(answer, result)


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

n = mint()
c = [0]*1005
while n%2 == 0:
	n //= 2
	c[2] += 1
i = 3
while i*i <= n:
	while n%i == 0:
		n //= i
		c[i] += 1
	i += 2
m = 0
r = 1
for i in range(len(c)):
	m = max(m, c[i])
	if c[i] != 0:
		r *= i
if n != 1:
	m = max(m, 1)
	r *= n
k = 0
i = 0
while m > (1<<i):
	i += 1
mm = 1<<i
for j in range(len(c)):
	if c[j] != 0 and mm != c[j]:
		k = 1
if n != 1 and mm != 1:
	k = 1
print(r, i+k)


from math import log, ceil
n = int(input())

d = {}

def prime_fac(n):
    nonlocal d
    i = 2
    while i <= n:
        while n % i == 0 and i <= n:
            n //= i
            d[i] = d.get(i, 0) + 1
        i += 1
 
if n == 1:
    print(1, 0)
else:
    prime_fac(n)
    m = d[max(d, key=lambda x: d[x])]
    prod = 1
    for i in d:
        prod *= i
    if m in [2**i for i in range(50)] and len(set(d.values())) == 1:
        print(prod, int(log(m, 2)))
    else:
        print(prod, ceil(log(m, 2)) + 1)

from math import *
def fct(n):

  res = []
  sqfree = 1
  for p in range(2, int(sqrt(n) + 10)):
    cnt = 0
    while n % p == 0:
      cnt += 1
      n //= p
    if cnt > 0:
      res.append(cnt)
      sqfree *= p

  if n != 1:
    res.append(1)
    sqfree *= n
  return res, sqfree

def solve(n):
  if n == 1: return (1, 0)
  fctr, sqfree = fct(n)
  # print("fctr = ", fctr)
  mx = max(fctr)
  # print("mx = ", mx)
  next_pow2 = 2**ceil(log(mx)/log(2))

  # print("next_pow2  = ", next_pow2)
  times = 0
  if (any(x != next_pow2 for x in fctr)):
    times += 1

  while next_pow2 != 1:
    next_pow2 //= 2
    times += 1

  return sqfree, times

print(*solve(int(input())))


#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)
re = 1
mc = 1
zc = []
for i in range(2, 10000):
    if N%i != 0 : continue
    re *= i
    c = 0
    while N%i==0:
        N//=i
        c+=1
    
    zc.append(c)
if N>1:
    re*=N
    zc.append(1)
if zc:
    mc = max(zc)
t =1 
for i in range(100):
    if mc<=t:
        break
    t*=2
dprint(t)
dprint(zc)
g = i
for x in zc:
    if x<t:
        g+=1
        break

print(re,g)




n = int(input())
if n == 1:
    print(1, 0)
    return
cnts = []
i = 2
result = 1
while i * i <= n:
    if n % i == 0:
        result *= i
        c = 0
        while n % i == 0:
            c += 1
            n //= i
        cnts.append(c)
    i += 1
if n > 1:
    cnts.append(1)
    result *= n
m = 0
if not (cnts.count(cnts[0]) == len(cnts) and cnts[0] & (cnts[0] - 1) == 0):
    m += 1
    d = max(cnts)
    r = 1
    while r < d:
        r <<= 1
        m += 1
else:
    d = max(cnts)
    while d != 1:
        m += 1
        d >>= 1
print(result, m)
        


import sys
from math import sqrt, log, ceil
input_file = sys.stdin

n = int(input_file.readline())

def factor(n):
    lst = []
    prod = 1
    for i in range(2, n+1):
        if n % i == 0:
            prod *= i
            lst.append(0)
            while n % i == 0:
                lst[-1] += 1
                n /= i
        if n < i:
            break
    return lst, prod

if n == 1:
    print(1, 0)
else:
    lst, ans = factor(n)
    maxi, mini = max(lst), min(lst)
    if maxi == mini and log(maxi, 2) == int(log(maxi, 2)):
        print(ans, int(log(maxi, 2)))
    else:
        print(ans, int(ceil(log(maxi, 2)) + 1))


import math
import sys
x=int(input())

if x==1:
    print(1,0)
    return

TWO=[2**i for i in range(30)]

xr=math.ceil(math.sqrt(x))

LIST=[]
for i in range(2,xr+2):
    if x%i==0:
        while x%i==0:
            LIST.append(i)
            x=x//i
    else:
        i+=1
if x!=1:
    LIST.append(x)

from collections import Counter
counter=Counter(LIST)

ANS=1
for l in list(counter.keys()):
    ANS*=l

count=max(counter.values())

for i in range(30):
    if count<=TWO[i]:
        break

if max(counter.values())==min(counter.values()) and TWO[i]==max(counter.values()):
    ANS2=i
else:
    ANS2=i+1

print(ANS,ANS2)


n = int(input())

num = 1
maxPow = 1
minPow = 9999

for i in range(2, n + 1):
  if (n % i == 0):
    power = 0

    while(n % i == 0):
      power += 1
      n = n // i

    num *= i

    maxPow = max(maxPow, power)
    minPow = min(minPow, power)

i = 1
power = 0

while(i < maxPow):
  i *= 2
  power += 1

if(i != maxPow):
  power += 1
elif(minPow < maxPow):
  power += 1

print(num, power)

from math import log, ceil
d = {}
n = int(input())
if n == 1:
    print('1 0')
    return
i = 2
while True:
    if i > n:
        break
    if n % i == 0:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
        n //= i
    else:
        i += 1

maxpow = max(d.values())
minpow = min(d.values())
ans = int(ceil(log(maxpow, 2)))
if maxpow & (maxpow - 1) != 0:
    ans += 1
elif minpow != maxpow:
    ans += 1
value = 1
for i in d.keys():
    value *= i
print(value, ans)

primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
sisu=[0]*168
nn=int(input())
n=int(nn)
for i in range(168):
    while True:
        if n%primes[i]==0:
            n//=primes[i]
            sisu[i]+=1
        else:
            break
ans=1
maxsisu=0
if n>1:
    sisu.append(1)
    primes.append(n)
for i in range(len(sisu)):
    if sisu[i]>0:
        maxsisu=max(maxsisu,sisu[i])
        ans*=primes[i]
comp=1
ans2=0
while comp<maxsisu:
    comp*=2
    ans2+=1
for i in range(len(sisu)):
    if sisu[i]>0 and sisu[i]!=comp:
        ans2+=1
        break
print(ans,ans2)


# use this as the main template for python problems
from collections import Counter
import math

def primeFactors(n): 
      
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        yield 2
        n = n / 2
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,int(math.sqrt(n))+1,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            yield i
            n = n / i 
              
    # Condition if n is a prime 
    # number greater than 2 
    if n > 2: 
        yield n

def get_prime_factorization(n):
    if(n == 1):
        return {1 : 1}
    primes = {}
    for prime in primeFactors(n):
        prime = int(prime)
        if(prime in primes):
            primes[prime] += 1
        else:
            primes[prime] = 1
    return primes

def next_power_of_2(n):
    return int(math.pow(2, math.ceil(math.log(n)/math.log(2))))

def solution(n):

    pf = get_prime_factorization(n)
    
    lp = 0  
    for key, val in list(pf.items()):
        lp = max(lp, val)
   
    # lp is the largest power in the prime factorization
    # we need the nearest power of two
    np2 = next_power_of_2(lp)
    ans = 1
    for key, val in list(pf.items()):
        ans *= key
    
    moves = 0
    for key, val in list(pf.items()):
        if(val != np2):
            moves = 1
            break
    moves += int(math.log2(np2))

    print(ans, moves)



def __starting_point():

    # single variables
    n = [int(val) for val in input().split()][0]

    # solve it!
    solution(n)


__starting_point()

n = int(input())
primes = {}
for i in range(2, n):
	while n%i == 0:
		n /= i 
		if i in primes:
			primes[i] += 1
		else:
			primes[i] = 1
if len(primes) == 0:
	print(n, 0)
	return
from math import ceil, log2
pow2 = pow(2, ceil(log2(max(primes.values()))))
flag = 0
for i in primes:
	if primes[i] != pow2:
		flag = 1
		break
ans = 1
for i in primes:
	ans*=i
print(ans, int(log2(pow2)) + flag)

def user99():
    n = int(input())
    nn = n

    N = 10**6
    prime = [True] * N
    prime[0] = prime[1] = False;

    for i in range(2, N, 1):
        if i * i > N: break
        if prime[i]:
            for j in range(i * i, N, i):
                prime[j] = False

    primes = []
    for i in range(N):
        if prime[i]:
            primes.append(i)

    b = []
    for p in primes:
        if n % p != 0: continue
        power = 0
        while n % p == 0:
            n //= p
            power += 1
        b.append([p, power])

    steps, x = 0, 1

    max_power = 0
    for i in b:
        max_power = max(max_power, i[1])
        x *= i[0]

    for i in range(10):
        if max_power <= 2**i:
            max_power = 2**i
            steps = i
            break

    if x**(2**steps) != nn:
        steps += 1

    print(x, steps)

user99()

def factor(n):

    def factor_n(m):
        for q in range(2, m + 1):
            if m % q == 0:
                return q
            if q > m**(1/2):
                return m

    factors = {}
    while True:
        factor_naw = factor_n(n)
        n //= factor_naw
        factors[factor_naw] = factors.get(factor_naw, 0)+1
        if n == 1:
            break
    return factors


n = int(input())
if n == 1:
    print(n, 0)
else:
    a = factor(n)
    s = max(a.values())
    if s == 1:
        print(n, 0)
    else:
        q1, q2 = 1, 0
        while q1 < s:
            q1 *= 2
            q2 += 1
        answer = 1
        for q in a:
            answer *= q
        p = set(a.values())
        print(answer, q2+1 if len(set(a.values())) != 1 or 2**q2 != s else q2)


from functools import reduce

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

	if n == 1:
		print(1, 0)
		return
	
	fact = dict()
	d = 2
	c = 0
	while n % d == 0:
		c += 1
		n //= d
	if c > 0:
		fact[d] = c
	
	d = 3
	while n != 1:
		c = 0
		while n % d == 0:
			c += 1
			n //= d
		if c > 0:
			fact[d] = c
		d += 2

	ans = reduce(lambda x,y: x*y, fact.keys())
	maxPow = max(fact.values())

	x = 0
	while maxPow > (1 << x):
		x += 1

	if maxPow == (1 << x) and all([y == maxPow for y in fact.values()]):
		print(ans, x)
		return
	else:
		print(ans, x + 1)
		return

def __starting_point():
	main()
__starting_point()

def tp(n):
    k=1
    while k<n:
        k*=2
    return k
n=int(input())
a=[]
z=1
if n==1:
    print(1,0);return
for i in range(2,int(n**.5)+1):
    r=0
    if n%i==0:
        z*=i
    while n%i==0:
        n//=i
        r+=1
    if r>0:
        a.append(r)
if n>1:
    a.append(1)
    z*=n
l=max(a)
k=tp(l)
mo=0
fl=0
for i in a:
    if i!=k:
        fl=1
        break
while k!=1:
    k//=2
    mo+=1
if fl:
    print(z,mo+1)
else:
    print(z,mo)



    

from math import log, ceil


def factor1(n):
    num = 2
    res = set()
    while num ** 2 <= n:
        while n % num == 0:
            res.add(num)
            n = n // num
        num += 1
    if n > 1:
        res.add(n)
    ans = 1
    for x in res:
        ans *= x
    return ans


def factor(n):
    num = 2
    res = dict()
    while num ** 2 <= n:
        while n % num == 0:
            res[num] = res.get(num, 0) + 1
            n = n // num
        num += 1
    if n > 1:
        res[n] = res.get(n, 0) + 1
    return res


n = int(input())
min_ = factor1(n)
kek = sorted(factor(n).values())
if min_ == n:
    print(n, 0)
elif kek[0] == kek[-1] and log(kek[-1], 2) // 1 == log(kek[-1], 2):
    print(min_, int(log(kek[-1], 2)))
else:
    print(min_, ceil(log(kek[-1], 2)) + 1)


def natlog(mx):
    maxpower = 0
    while mx > 1:
        mx = (mx+1) // 2
        maxpower += 1
    return maxpower

from collections import Counter
n = int(input())

if n == 1:
    print(1, 0)
    return

j = 2
setres  = Counter()

while n>1:
    if n % j == 0:
        n = n//j
        setres[j] += 1
    else:
        j+= 1

res = 1
for j in setres:
    res *= j
# print(res, setres, setres.most_common(1))
maxpower = natlog(setres.most_common(1)[0][1])
maxnum = 2**maxpower

cnt_actions = maxpower

for j, p in list(setres.items()):
    if p < maxnum:
        cnt_actions += 1
        break

print(res, cnt_actions)



def main():
    buf = input()
    n = int(buf)
    op_count = 0
    factor = prime_factorization(n)
    c_max = 1
    first_c = None
    all_same = True
    min_number = 1
    for f, c in list(factor.items()):
        if c > c_max:
            c_max = c
        if first_c == None:
            first_c = c
        elif c != first_c:
            all_same = False
        min_number *= f
    if check_power_of_2(c_max) and all_same:
        pass
    else:
        op_count += 1
    if not check_power_of_2(c_max):
        c_max = c_max << 1
        c_max = c_max & (c_max - 1)
    while c_max > 1:
        c_max //= 2
        op_count += 1
    print(min_number, op_count)


def check_power_of_2(x):
    return (x != 0) and ((x & (x - 1)) == 0)

def prime_factorization(number):
    n = number
    i = 2
    factor = {}
    while i * i <= n:
        while n % i == 0:
            if i in factor:
                factor[i] += 1
            else:
                factor.update({i : 1})
            n //= i
        i += 1
    if n > 1 or not factor:
        if n in factor:
            factor[n] += 1
        else:
            factor.update({n : 1})
    return factor


def __starting_point():
    main()

__starting_point()

n = int(input())
fac = {}
nn = n
maxe = 1
while nn%2 == 0:
    fac[2] = fac.get(2, 0) + 1
    nn >>= 1
for i in range(3, nn+1, 2):
    if i*i > nn:
        break
    while nn%i == 0:
        fac[i] = fac.get(i, 0) + 1
        nn //= i
if nn > 1:
    fac[nn] = 1
# print(nn)
# print(fac)

maxe = 1
mine = n
prod = 1
for f in fac:
    if fac[f] > maxe:
        maxe = fac[f]
    if fac[f] < mine:
        mine = fac[f]
    prod *= f
ops = 0
t = 1
while t < maxe:
    t <<= 1
    ops += 1
if mine < t:
    ops += 1
print(prod, ops)