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.

Source: codeforces | Difficulty: MEDIUM
Tags: Number theory

Mathematics

Greedy algorithms


Solutions:
n = int(input())
ans = 1
temp = n
ans = 1
c = 0
for i in range(2, n + 1):
	if n % i == 0:
		ans *= i
		while n % i == 0:
			n /= i
ans2 = ans
while ans % temp > 0:
	ans *= ans
	c += 1
if ans > temp:
	c += 1
print(ans2, c)


n = int(input())
if n == 1:
	print(1, 0)
else:
	r = 1
	t = n
	w = []
	for i in range(2, t + 1):
		if n % i == 0:
			r *= i
			c = 0
			while n % i == 0:
				n //= i
				c += 1
			if c > 0:
				w.append(c)
		if n == 1:
			break
	l = len(w)
	a = []
	q = 0
	for i in range(l):
		c = 0
		k = w[i]
		while k:
			k //= 2
			c += 1
		if w[i] % 2 ** (c - 1) == 0:
			a.append(c - 1)
			q = max(c - 1, q)
		else:
			a.append(c)
			q = max(c, q)
	if len(set(a)) == 1:
		f = 0
		for i in w:
			if i % 2 ** q != 0:
				f = 1
				break
		if f:
			print(r, q + 1)
		else:
			print(r, q)
	else:
		print(r, q + 1)


from math import *

def primeFactors(n, dict1):
	while n % 2 == 0:
		try:
			dict1[2] += 1
		except:
			KeyError
			dict1[2] = 1
		n = n // 2
	for i in range(3, floor(sqrt(n)) + 1, 2):
		while n % i == 0:
			try:
				dict1[i] += 1
			except:
				KeyError
				dict1[i] = 1
			n = n // i
	if n > 2:
		try:
			dict1[n] += 1
		except:
			KeyError
			dict1[n] = 1
n = int(input())
if n == 1:
	print(1, 0)
else:
	dict1 = {}
	primeFactors(n, dict1)
	ans = 1
	arr = []
	for i in dict1.keys():
		ans = ans * i
		arr.append(dict1[i])
	if len(arr) == arr.count(arr[0]):
		if ceil(log2(arr[0])) == floor(log2(arr[0])):
			print(ans, floor(log2(arr[0])))
		else:
			print(ans, 1 + ceil(log2(arr[0])))
	else:
		maxval = max(arr)
		print(ans, 1 + ceil(log2(maxval)))


import math

def sieve(n):
	mark = [0] * (n + 1)
	prime = []
	for i in range(3, n + 1, 2):
		if not mark[i]:
			for j in range(3 * i, n + 1, i + i):
				mark[j] = 1
	prime.append(2)
	for i in range(3, n + 1, 2):
		if not mark[i]:
			prime.append(i)
	return prime

def ispowerof2(x):
	if x and (not x & x - 1):
		return 0
	else:
		return 1
n = int(input())
prime = sieve(n)
l = []
countp = 0
ans = 1
for i in prime:
	countp = 0
	if n % i == 0:
		ans *= i
		while n % i == 0:
			n //= i
			countp += 1
		l.append(countp)
	if n == 1:
		break
if len(l) != 0:
	maxp = max(l)
else:
	maxp = 0
flag = 0
for i in l:
	if i != maxp:
		flag = 1
temp = 0
if flag:
	temp = 1
else:
	temp = ispowerof2(maxp)
if maxp == 1:
	maxp -= 1
elif maxp != 0:
	maxp = math.ceil(math.log2(maxp)) + temp
print(ans, maxp)


n = int(input())
n1 = n
ans = 1
maxcnt = 0
flag = 0
for i in range(2, n1 + 1):
	if i > n:
		break
	if n % i == 0:
		ans *= i
		cnt = 0
		while n % i == 0:
			n /= i
			cnt += 1
		if cnt != maxcnt and maxcnt > 0:
			flag = 1
		if cnt > maxcnt:
			maxcnt = cnt
myb = [1, 2, 4, 8, 16, 32]
if maxcnt > 0:
	if maxcnt not in myb:
		flag = 1
for i in range(len(myb)):
	if myb[i] >= maxcnt:
		anscnt = i
		break
print(ans, anscnt + flag)


from collections import defaultdict
from math import log, ceil
k = int(input())
n = k // 2
primefac = defaultdict(int)
mark = [True] * (n + 1)
for i in range(2, n + 1):
	if mark[i]:
		while k != 1:
			if k % i == 0:
				k //= i
				primefac[i] += 1
			else:
				break
		if k == 1:
			break
		for j in range(i, n + 1, i):
			mark[j] = False
if k != 1:
	print(k, 0)
else:
	ans1 = 1
	ans2 = 0
	k = 0
	for value in primefac.values():
		t = value
		break
	for (key, value) in primefac.items():
		te = log(value, 2)
		if t != value:
			k = 1
		if te != int(te):
			k = 1
		ans1 *= key
		ans2 = max(ans2, ceil(te))
	print(ans1, ans2 + k)


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))


from math import sqrt
n = int(input())
s = 0
f = 0
while int(sqrt(n)) == sqrt(n) and n > 1:
	n = int(sqrt(n))
	s += 1
for i in range(int(sqrt(n)), 1, -1):
	while n % (i * i) == 0:
		s += 1
		n //= i
		f = 1
print(n, s + f)


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()


import math
import collections
import bisect
import heapq
import time
import itertools
import sys
N = int(input())
factors = collections.defaultdict(int)
primes = [True for _ in range(max(1 + N // 2, 10))]
primes[0] = primes[1] = False
for i in range(2, N // 2 + 1):
	if primes[i]:
		t = 2
		while i * t <= N // 2:
			primes[i * t] = False
			t += 1
n = N
for i in range(2, N // 2 + 1):
	if not primes[i]:
		continue
	while i <= n and n % i == 0:
		n //= i
		factors[i] += 1

def dpow(x):
	u = int(math.log2(x))
	p = 1 << u
	if p < x:
		return u + 1
	else:
		return u
vals = list(factors.values())
U = [dpow(a) for a in vals]
if not U:
	print(N, 0)
else:
	ans = 1
	for v in factors.keys():
		ans *= v
	u = max(U)
	if all((2 ** u == vals[i] for i in range(len(vals)))):
		print(ans, u)
	else:
		print(ans, u + 1)


n = int(input())
d = {}
i = 2
while i <= n:
	if n % i == 0:
		d[i] = 1
		n = n // i
		while n % i == 0:
			d[i] += 1
			n = n // i
	i += 1
temp = 1
ans = 1
ans2 = 1
c = 0
for (i, j) in d.items():
	if c == 0:
		ans = j
		ans2 = j
	ans = max(ans, j)
	ans2 = min(ans2, j)
	temp *= i
	c += 1
i = 1
a = 0
while i < ans:
	i *= 2
	a += 1
if ans == ans2 and i == ans:
	print(temp, a)
else:
	print(temp, a + 1)


from collections import defaultdict
i = 2
n = int(input())
dic = defaultdict(lambda : 0)
while n > 1:
	if n % i == 0:
		n //= i
		dic[i] += 1
	else:
		i += 1
arr = list(dic.values())
ln = len(arr)
ans = [1, 0]
for el in dic.keys():
	ans[0] *= el
temp = 0
while True:
	onc = 0
	for i in range(ln):
		if arr[i] == 1:
			onc += 1
		if arr[i] % 2 == 1:
			arr[i] += 1
			temp += 1
		arr[i] //= 2
	if onc == ln:
		break
	ans[1] += 1
ans[1] += 1 if temp > ln and ans[1] > 0 else 0
print(*ans)


from math import sqrt, ceil, log

class Solve:

	def __init__(self):
		n = int(input())
		prime = {}
		sq = int(sqrt(n)) + 1
		(N, cnt) = (1, 0)
		for i in range(2, sq):
			if n % i == 0:
				prime[i] = 0
				N *= i
				while n % i == 0:
					n //= i
					prime[i] += 1
		if n > 1:
			prime[n] = 1
			N *= n
		(mx, mn) = (0, 35)
		for data in prime:
			mx = max(mx, prime[data])
			mn = min(mn, prime[data])
		if N == 1:
			cnt = 0
		else:
			cnt = int(ceil(log(mx, 2))) + (0 if mx == mn and mx in [1, 2, 4, 8, 16] else 1)
		print(N, cnt)

def main():
	s = Solve()
main()


def factorize(n):
	factors = []
	for i in range(2, int(n ** 0.5) + 1):
		cnt = 0
		while n % i == 0:
			n //= i
			cnt += 1
		if cnt > 0:
			factors.append((i, cnt))
	if n > 1:
		factors.append((n, 1))
	return factors
n = int(input())
factors = factorize(n)
ans1 = 1
max_c = 1
for (f, c) in factors:
	ans1 *= f
	max_c = max(max_c, c)
for i in range(10):
	if 2 ** i >= max_c:
		ans2 = 0
		for (_, c) in factors:
			if 2 ** i > c:
				ans2 = 1
		ans2 += i
		print(ans1, ans2)
		break


from math import log
import math

def prime(n):
	while n % 2 == 0:
		lis.append(2)
		has[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			lis.append(i)
			has[i] += 1
			n = n / i
	if n > 2:
		lis.append(n)
		has[int(n)] += 1
n = int(input())
if n == 1:
	print(1, 0)
	exit()
lis = []
has = [0] * 1000000
prime(n)
ans = c = 1
a = list(set(lis))
for i in a:
	ans *= i
m = max(has)
while c < m:
	c *= 2
ans2 = int(log(c, 2))
if c == m and has.count(m) == len(a):
	k = 0
else:
	ans2 += 1
print(int(ans), ans2)


n = int(input())
sl_vhoshd = {}
temp = 1
if n == 1:
	print(1, 0)
	exit()

def factor(n):
	rasl = []
	d = 2
	while d * d <= n:
		if n % d == 0:
			rasl.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		rasl.append(n)
	return rasl

def sled_st_dv(n):
	temp = 0
	while pow(2, temp) < n:
		temp += 1
	return temp

def proisv(mas):
	t = 1
	for i in mas:
		t *= i
	return t

def proverka(sl_vh, n):
	temp = 0
	t1 = 0
	sett = list(set(sl_vh.values()))
	while pow(2, temp) < sett[0]:
		temp += 1
	if sett[0] != pow(2, temp) or len(sett) > 1:
		return 0
	return -1
fact = factor(n)
sett = set(fact)
for i in fact:
	if i in sl_vhoshd:
		sl_vhoshd[i] += 1
	else:
		sl_vhoshd[i] = 1
temp += sled_st_dv(max(sl_vhoshd.values())) + proverka(sl_vhoshd, n)
print(proisv(sett), temp)


n = int(input())
ansA = 1
ansB = 0
_n = n
i = 2
while i * i <= n:
	if n % i == 0:
		ansA *= i
		while n % i == 0:
			n /= i
	i += 1
if n > 1:
	ansA *= n
tmp = ansA
print(int(ansA), end=' ')
while tmp % _n != 0:
	tmp *= tmp
	ansB += 1
if tmp != _n:
	ansB += 1
print(int(ansB))


import math
n = int(input())
yin = []
ans1 = 1
for i in range(2, n):
	if n % i == 0:
		num = 0
		while n % i == 0:
			num += 1
			n /= i
		s = [num, i]
		yin.append(s)
		ans1 = ans1 * i
if ans1 == 1:
	print(n, 0)
else:
	yin.sort(reverse=True)
	maxy = yin[0][0]
	miny = yin[-1][0]
	ans2 = 0
	x = 1
	while maxy > x:
		x = x * 2
		ans2 += 1
	if x == maxy and maxy == miny:
		ans2 += 0
	else:
		ans2 += 1
	print(ans1, ans2)


N = int(input())
prime_factors = {}
i = 2
while True:
	if i * i > N:
		if N in prime_factors:
			prime_factors[N] += 1
		else:
			prime_factors[N] = 1
		break
	if N % i == 0:
		if i in prime_factors:
			prime_factors[i] += 1
		else:
			prime_factors[i] = 1
		N //= i
		continue
	i += 1
ans1 = 1
for prime in prime_factors.keys():
	ans1 *= prime
ans2 = 0
while 1 << ans2 < max(prime_factors.values()):
	ans2 += 1
ans2 += 1
temp = list(prime_factors.values())[0]
for num in prime_factors.values():
	if temp != num:
		break
else:
	while temp % 2 == 0:
		temp //= 2
	if temp == 1:
		ans2 -= 1
print(ans1, ans2)


from math import *
n = int(input())
primesfactors = []
pfpowerlist = []
powerscount = []
prime = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p * 2, n + 1, p):
			prime[i] = False
	p += 1
for p in range(2, n):
	if prime[p]:
		primesfactors.append(p)
finalAns = 1
for i in primesfactors:
	if n % i == 0:
		finalAns *= i
	while n % i == 0:
		n = n / i
		pfpowerlist.append(i)
for i in primesfactors:
	if pfpowerlist.count(i) != 0:
		powerscount.append(pfpowerlist.count(i))
if len(pfpowerlist) == 0:
	print(n, '0')
	exit(0)
high = max(powerscount)
low = min(powerscount)
logvalue = log(high, 2)
if high == low:
	if logvalue.is_integer():
		print(finalAns, int(logvalue))
	else:
		print(finalAns, int(logvalue) + 2)
elif logvalue.is_integer():
	print(finalAns, int(logvalue) + 1)
else:
	print(finalAns, int(logvalue) + 2)


import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict
inp = sys.stdin.readline
read = lambda : list(map(int, inp().strip().split()))

def solve():
	n = int(inp())
	if n == 1:
		print(1, 0)
		exit()
	arr = []
	m_c = 1
	sett = set()
	for i in range(2, int(sqrt(n) + 1)):
		c = 0
		if n % i == 0:
			arr.append(i)
			while n % i == 0:
				c += 1
				n //= i
			sett.add(c)
		m_c = max(m_c, c)
	if n > 1:
		arr.append(n)
		sett.add(1)
	m_c = ceil(log(m_c, 2))
	if len(sett) == 1 and 2 ** m_c in sett:
		ans = 1
		for i in arr:
			ans *= i
		print(ans, m_c)
	else:
		ans = 1
		for i in arr:
			ans *= i
		print(ans, m_c + 1)
solve()


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 collections import defaultdict
import math

def getPrimeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	k = 3
	while k * k <= n:
		if n % k == 0:
			n = n // k
			factors.append(k)
		else:
			k += 2
	if n > 1:
		factors.append(n)
	return factors
n = int(input())
if n == 1:
	print('1 0')
	exit(0)
counts = defaultdict(int)
for a in getPrimeFactors(n):
	counts[a] += 1
k = list(counts.values())[0]
no = 1
notsame = False
for (a, cnt) in counts.items():
	no *= a
	if k != cnt:
		notsame = True
	k = max(k, cnt)
moves = math.ceil(math.log2(k))
if moves != math.log2(k) and moves != 0:
	notsame = True
if notsame:
	moves += 1
print(f'{no} {moves}')


n = int(input())
copy = n
q = []
bas = []
co = 0
while n % 2 == 0:
	n //= 2
	co += 1
if co != 0:
	q += [co]
	bas += [2]
for i in range(3, n + 1, +2):
	co = 0
	while n % i == 0:
		n //= i
		co += 1
	if co != 0:
		q += [co]
		bas += [i]
x = 0
w = 1
if copy == 1:
	exit(print(copy, 0))
for i in bas:
	w *= i
while 2 ** x < max(q):
	x += 1
if 2 ** x == max(q):
	if all((i == max(q) for i in q)):
		print(w, x)
	else:
		print(w, x + 1)
else:
	print(w, x + 1)


import math

def myf(n):
	if n == 1:
		return [(1, 1)]
	a = list()
	for i in range(2, n + 1):
		if n % i == 0:
			count = 0
			while n % i == 0:
				n /= i
				count += 1
			a.append((i, count))
	return a
n = int(input())
s = -1
x = myf(n)
h = True
for i in range(1, len(x)):
	if x[i][1] != x[i - 1][1]:
		h = False
if h:
	if x[0][1] & x[0][1] - 1 == 0:
		s = math.log2(x[0][1])
	else:
		mym = x[0][1]
		if mym & mym - 1 != 0:
			s = 0
		while mym != 0:
			mym = mym >> 1
			s += 1
		s += 1
else:
	mym = x[0][1]
	for each in x:
		if each[1] > mym:
			mym = each[1]
	if mym & mym - 1 != 0:
		s = 0
	while mym != 0:
		mym = mym >> 1
		s += 1
	s += 1
v = 1
for each in x:
	v *= each[0]
print(v, int(s), sep=' ')


import sys
n = int(input())
k = n
s = dict()
if n == 1:
	print(1, 0)
	sys.exit()
for p in range(2, int(n ** 0.5) + 1):
	while n % p == 0:
		if p not in s:
			s.update({p: 1})
		else:
			s[p] += 1
		n //= p
if n > 1:
	s.update({n: 1})
sm = 1
for j in s:
	sm *= j
m = max(s.values())
p = 1
e = 0
while p < m:
	p *= 2
	e += 1
if sm ** p == k:
	e -= 1
print(sm, e + 1)


n = int(input())
if n == 1:
	print(1, 0)
	exit(0)
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
		mindegree = min(mindegree, multiplicity)
		maxdegree = max(maxdegree, multiplicity)
if 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)


def ii():
	return int(input())

def mi():
	return 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)


from collections import defaultdict
import math

def primeFactors(n):
	prime = defaultdict(int)
	while n % 2 == 0:
		prime[2] += 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			prime[i] += 1
			n = n // i
	if n > 2:
		prime[n] += 1
	return prime
n = int(input())
if n == 1:
	print(1, 0)
else:
	d = primeFactors(n)
	prod = 1
	for (k, v) in d.items():
		prod *= k
	mx = max(d.values())
	moves = 0
	while 2 ** moves < mx:
		moves += 1
	for i in d.values():
		if i != 2 ** moves:
			moves += 1
			break
	print(prod, moves)


from math import sqrt, ceil, log2

def factor(n):
	potentional_p = 3
	itog_list = {}
	if n % 2 == 0:
		itog_list[2] = 0
	while n % 2 == 0:
		n = n // 2
		itog_list[2] += 1
	while n - 1:
		if potentional_p > sqrt(n):
			if n in itog_list:
				itog_list[n] += 1
			else:
				itog_list[n] = 1
			return itog_list
		while n % potentional_p == 0:
			n = n // potentional_p
			if potentional_p in itog_list:
				itog_list[potentional_p] += 1
			else:
				itog_list[potentional_p] = 1
		potentional_p += 2
	return itog_list
n = int(input())
if n == 1:
	print(1, 0)
	exit(0)
F = factor(n)
ans = 1
ma = 0
mi = 10 ** 9
for i in F:
	ans *= i
	ma = max(ma, F[i])
	mi = min(mi, F[i])
ddd = ma
while ddd > 1:
	if ddd % 2 == 0:
		ddd //= 2
	else:
		break
kek = ddd == 1
if ma == mi and kek:
	print(ans, ceil(log2(ma)))
else:
	print(ans, 1 + ceil(log2(ma)))


from queue import PriorityQueue
from queue import Queue
import math
from collections import defaultdict
import sys
import operator as op
from functools import reduce
n = int(input())
if n == 1:
	print(1, 0)
else:
	ar = [-1 for k in range(n + 1)]
	for k in range(2, n + 1):
		if ar[k] == -1:
			for j in range(k, n + 1, k):
				ar[j] = k
	d = defaultdict(lambda : 0)
	n1 = n
	while n1 > 1:
		d[ar[n1]] += 1
		n1 = n1 // ar[n1]
	m = 0
	fl = 0
	res = 1
	prev = 0
	for (k, j) in d.items():
		res *= k
		if prev != 0 and prev != j:
			fl = 1
		else:
			prev = j
		m = max(m, j)
	if math.log2(m) != int(math.log2(m)):
		fl = 1
	print(res, math.ceil(math.log2(m)) + fl)


import collections
import math
import sys

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def primefactors(n):
	d = collections.defaultdict(int)
	while n % 2 == 0:
		d[2] += 1
		n /= 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			d[i] += 1
			n /= i
	if n > 2:
		d[n] += 1
	return d
n = int(input())
if n == 1:
	print(1, 0)
	sys.exit()
x = primefactors(n)
y = max(x.values())
z = x.keys()
k = 1
for i in z:
	k *= i
if y == 1:
	print(int(k), 0)
elif isPowerOfTwo(y):
	if len(set(x.values())) == 1:
		print(int(k), int(math.log2(y)))
	else:
		print(int(k), int(math.log2(y) + 1))
else:
	print(int(k), math.ceil(math.log2(y)) + 1)


def smol(n):
	prod = 1
	orig = n
	d = 2
	while d * d <= orig and n > 1:
		if n % d == 0:
			prod *= d
			while n % d == 0:
				n //= d
		d += 1
	if n > 1:
		prod *= n
	return prod
num = int(input())
small = smol(num)
ans = 0
while small % num > 0:
	small *= small
	ans += 1
if small != num:
	ans += 1
print(smol(num), ans)


from collections import Counter
import math

def primeFactors(n):
	while n % 2 == 0:
		yield 2
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			yield i
			n = n / i
	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)
	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():
	n = [int(val) for val in input().split()][0]
	solution(n)
__starting_point()


import math

def primeFactors(n):
	d = {}
	while n % 2 == 0:
		if 2 not in d.keys():
			d[2] = 1
		else:
			d[2] += 1
		n = n // 2
	for i in range(3, int(math.sqrt(n) + 1), 2):
		while n % i == 0:
			if i not in d.keys():
				d[i] = 1
			else:
				d[i] += 1
			n = n // i
	if n > 2:
		d[n] = 1
	return d

def all_one(d):
	for i in d.keys():
		if d[i] != 1:
			return False
	return True

def solve(d):
	maxx = 0
	n = 1
	for i in d.keys():
		maxx = max(maxx, d[i])
		n = n * i
	flag = 1
	curr = -1
	for i in d.keys():
		if curr == -1:
			curr = d[i]
		elif curr != d[i]:
			flag = 0
			break
	if flag == 1 and int(math.log(curr, 2)) == math.log(curr, 2):
		count = 0
	else:
		count = 1
	i = 1
	while i < maxx:
		i = i * 2
		count += 1
	return (n, count)
n = int(input())
if n == 1:
	print(1, 0)
else:
	d = primeFactors(n)
	if all_one(d):
		print(n, 0)
	else:
		(n, count) = solve(d)
		print(n, count)


import math
from typing import Dict, List, Tuple

def input_lst() -> List[int]:
	return [int(x) for x in input().split()]

def print_out(res: List[int]):
	print(' '.join([str(x) for x in res]))

def get_primes(n: int) -> List[int]:
	max_n = n
	rng = list(range(max_n + 1))
	rng[0] = 1
	rng[1] = 1
	primes = []
	for i in range(2, max_n + 1):
		if rng[i] > 1:
			primes.append(i)
			for j in range(i + i, max_n + 1, i):
				rng[j] = 0
	return primes

def main():
	(n,) = (int(x) for x in input().split())
	if n == 1:
		print('1 0')
		return
	primes = get_primes(n)
	factors = [0] * len(primes)
	for prime_id in range(len(primes)):
		prime = primes[prime_id]
		i = 1
		while n % prime ** i == 0:
			i += 1
		factors[prime_id] = i - 1
	max_factor = max(factors)
	need_to_mul = False
	min_number = 1
	for (i, factor) in enumerate(factors):
		if not (factor == 0 or factor == max_factor):
			need_to_mul = True
		if factor > 0:
			min_number *= primes[i]
	squares_count_float = math.log(max_factor, 2)
	squares_count = math.ceil(squares_count_float)
	if squares_count != math.floor(squares_count_float):
		need_to_mul = True
	if need_to_mul:
		squares_count += 1
	print('{} {}'.format(min_number, squares_count))
main()


import math
n = int(input())
(ans, anssq, flag) = (1, 0, 0)
maxsq = 1
tempn = n
for i in range(2, n + 1):
	tempsq = 0
	tempflag = 0
	while tempn % i == 0:
		tempn = tempn // i
		tempsq += 1
		tempflag += 1
	if tempsq > 0:
		ans = ans * i
	if flag == 0 and tempflag != 0:
		flag = tempflag
	elif flag > 0 and tempflag != 0 and (tempflag != flag):
		flag = -1
	if tempsq > maxsq:
		maxsq = tempsq
if math.log2(maxsq) == 0.0:
	print(ans, 0)
elif flag == -1:
	print(ans, math.ceil(math.log2(maxsq) + 1))
elif math.ceil(math.log2(maxsq)) == math.log2(maxsq):
	print(ans, math.ceil(math.log2(maxsq)))
else:
	print(ans, math.ceil(math.log2(maxsq) + 1))


import math
n = int(input())
N = n
frq = list()
for i in range(n + 1):
	if i == 1:
		frq.append(1)
	frq.append(0)
while n > 1:
	for i in range(2, n + 1):
		if n % i == 0:
			frq[i] += 1
			n //= i
			break
maxfrq = 0
sqfree = 1
parity = False
for i in range(N + 1):
	if frq[i] > 0:
		sqfree *= i
	maxfrq = max(maxfrq, frq[i])
if int(math.log2(maxfrq)) != math.log2(maxfrq):
	parity = True
for i in range(2, N + 1):
	if frq[i] > 0 and frq[i] != maxfrq:
		parity = True
		break
nextbit = 1
while nextbit < maxfrq:
	nextbit *= 2
if parity == False:
	nextbit /= 2
print(sqfree, int(math.log2(nextbit)) + 1)


m = 10 ** 6 + 5
cri = [0] * m
for i in range(2, m):
	if cri[i] == 0:
		cri[i] = i
		for j in range(i * i, m, i):
			cri[j] = i
cri[1] = 1
n = int(input())
a = n
res = []
pp = 1
while a > 1:
	b = cri[a]
	pp *= b
	c = 0
	while a % b == 0 and a > 1:
		a //= b
		c += 1
	res.append(c)
if not res:
	res.append(1)
maxres = max(res)
minres = min(res)
aa = 1
ne = 0
while aa < maxres:
	aa *= 2
	ne += 1
ne += 1 if minres < aa else 0
print(pp, ne)


n = int(input())
i = 2
m = [0] * 1000003
mic = 10000003
a = 1
b = 0
while i * i <= n:
	if n % i == 0:
		while n % i == 0:
			n //= i
			m[i] += 1
		c = m[i]
		d = 0
		while c % 2 == 0:
			d += 1
			c //= 2
		mic = min(mic, d)
		a *= i
	i += 1
if n != 1:
	m[n] += 1
	c = m[n]
	d = 0
	while c % 2 == 0:
		d += 1
		c //= 2
	mic = min(mic, d)
	a *= n
	n = 1
k = 1
mi = 1
if mic != 10000003:
	b += mic
	for i in range(mic):
		mi *= 2
mx = 0
for i in range(1000003):
	if m[i] > 0:
		m[i] //= mi
		mx = max(mx, m[i])
while k < mx:
	k *= 2
	b += 1
fl = 0
for i in range(1000003):
	if m[i] > 0:
		if m[i] < k:
			fl = 1
print(a, b + fl)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 5)
from queue import PriorityQueue
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop
import math as mt
MAXN = 1000001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
n = int(input())
sieve()
z = getFactorization(n)
hash = defaultdict(int)
for i in z:
	hash[i] += 1
ans = 1
maxi = 0
flag = 0
seti = set()
for i in hash:
	ans *= i
	maxi = max(maxi, ceil(log2(hash[i])))
for i in hash:
	if log2(hash[i]) != maxi:
		flag += 1
		break
print(ans, maxi + flag)


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)
	exit(0)
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)


n = int(input())
if n == 1:
	print(1, 0)
	exit()
lis = []
x = int(n ** 0.5)
for i in range(2, x + 1):
	if n % i == 0:
		cnt = 0
		while n % i == 0:
			cnt += 1
			n //= i
		lis.append([i, cnt])
if n - 1:
	lis.append([n, 1])
su = 1
for i in lis:
	su *= i[0]
m = max([i[1] for i in lis])
import math
if 2 ** int(math.log(m, 2)) == m:
	if m == min([i[1] for i in lis]):
		m = int(math.log(m, 2))
	else:
		m = int(math.log(m, 2)) + 1
else:
	m = int(math.log(m, 2)) + 2
print(su, m)


import math
mul2 = [2 ** x for x in range(1, 7)]
n = int(input())
ncopy = n
facto = [0] * 1000001
ans = 1
cnt = 0
for i in range(2, math.ceil(n / 2) + 1):
	if n % i == 0:
		while n % i == 0:
			facto[i] += 1
			n //= i
		ans *= i
		cnt += 1
m = max(facto)
if m == 0:
	print(n, 0)
elif ncopy ** 0.5 == ans:
	print(ans, 1)
elif m == 1:
	print(ans, 0)
else:
	mi = 64
	lim = 0
	for each in mul2:
		if each - m >= 0 and each - m <= mi:
			mi = abs(m - each)
			lim = each
	times = int(math.log(lim, 2)) if cnt == 1 and lim == m else int(math.log(lim, 2)) + 1
	print(ans, times)


n = int(input())
if n == 1:
	print(1, 0)
	exit()
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 math

def list_primes_upto(upto: int):
	uptop1 = upto + 1
	uptom1 = upto - 1
	pcl = [True for x in range(uptop1)]
	lprimes = []
	if upto >= 2:
		lprimes.append(2)
	if upto >= 3:
		lprimes.append(3)
	i = 5
	while i < uptom1:
		ix2 = i * 2
		if pcl[i]:
			lprimes.append(i)
			for k in range(i * i, uptop1, ix2):
				pcl[k] = False
		ip2 = i + 2
		ip2x2 = ip2 * 2
		if pcl[ip2]:
			lprimes.append(ip2)
			for k in range(ip2 * ip2, uptop1, ip2x2):
				pcl[k] = False
		i += 6
	if i <= upto:
		ix2 = i * 2
		if pcl[i]:
			lprimes.append(i)
			for k in range(i * i, uptop1, ix2):
				pcl[k] = False
	return lprimes
n0 = int(input())
n = n0
lp = list_primes_upto(int(math.sqrt(n)) + 1)
ncp = 0
pmf = [0] * len(lp)
while ncp < len(lp) and n != 1:
	if n % lp[ncp] != 0:
		ncp += 1
		continue
	n //= lp[ncp]
	pmf[ncp] += 1
mn = n
sf = set(pmf)
if n != 1:
	sf.add(1)
for i in range(len(lp)):
	if pmf[i] == 0:
		continue
	mn *= lp[i]
if mn == n0:
	mo = 0
else:
	mpf = max(sf)
	impfl2 = int(math.log(mpf, 2))
	ls2 = [2 ** x for x in range(0, 1001)]
	ntm = 0
	for f in sf:
		if f == 0:
			continue
		if f not in ls2 or f != mpf:
			ntm = 1
			break
	if mpf in ls2:
		sro = impfl2
	else:
		sro = impfl2 + 1
		ntm = 1
	mo = ntm + sro
print(mn, mo)


from math import log

def pr(n):
	p = [x for x in range(3, n, 2)]
	for i in p:
		if i * i > n:
			break
		if i > 2:
			p[p.index(i) + i::i] = [2 for x in p[p.index(i) + i::i]]
	return sorted(list(set(p)))
x = int(input())
p = pr(1000000)
p2 = [2 ** x for x in range(20)]
x0 = x
n = 0
d = []
q = [0 for x in range(20)]
if x in p or x == 1:
	print(x, 0)
else:
	for i in p:
		if i * i > x:
			break
		if x % i == 0:
			n += 1
		while x % i == 0:
			x //= i
			d.append(i)
			q[n] += 1
	if x in p:
		q[n + 1] += 1
		d.append(x)
	d = list(set(d))
	q = set(q)
	q.remove(0)
	if max(q) == 1:
		print(x0, 0)
	else:
		x = 1
		for i in d:
			x *= i
		if max(q) == min(q) and max(q) in p2:
			print(x, int(log(max(q), 2)))
		elif max(q) in p2:
			print(x, int(log(max(q), 2)) + 1)
		else:
			print(x, int(log(max(q), 2)) + 2)


from math import log
from math import ceil, floor

def next_power_of_two(maxi):
	if floor(log(maxi, 2)) == ceil(log(maxi, 2)) and maxi != 1:
		power = 0
		while maxi > 1:
			maxi //= 2
			power += 1
		return power
	base = 2
	exp = 1
	while base ** exp < maxi:
		exp += 1
	return exp
from collections import defaultdict
n = int(input())
sieve = [True] * (n + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, int(n ** 0.5 + 1)):
	if sieve[i]:
		for j in range(i + i, n + 1, i):
			sieve[j] = False
number = 1
temp = n
factors = defaultdict()
div = 2
if n == 1:
	print(1, 0)
	exit(0)
while temp > 1:
	if temp % div != 0:
		div += 1
		continue
	temp //= div
	if div not in factors:
		factors[div] = 1
	else:
		factors[div] += 1
ops = 0
if len(factors) == 1:
	for (k, v) in factors.items():
		if k == n:
			print(k, 0)
		else:
			power = 2 ** next_power_of_two(v)
			if v != power:
				ops += 1
			while power > 1:
				power //= 2
				ops += 1
			print(k, ops)
	exit(0)
maxi = -1
for (k, v) in factors.items():
	number *= k
	maxi = max(maxi, v)
if maxi == 1:
	print(number, 0)
else:
	power = 2 ** next_power_of_two(maxi)
	if maxi != power:
		ops += 1
	else:
		for (k, v) in factors.items():
			if v != maxi:
				ops += 1
				break
	while power > 1:
		power //= 2
		ops += 1
	print(number, ops)


from sys import stdin, stdout
import collections

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
N = int(input())
p = prime_factors(N)
freq = {}
for num in p:
	if num not in freq:
		freq[num] = 1
	else:
		freq[num] += 1
final = 1
t = 0
for key in freq:
	final *= key
	t = max(t, freq[key])
res = 0
while True:
	if 2 ** res >= t:
		break
	res += 1
for key in freq:
	if freq[key] < 2 ** res:
		res += 1
		break
print(final, res)


import math
from collections import Counter

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	return l
n = int(input())
if n == 1:
	print('1 0')
elif True:
	l = primeFactors(n)
	k = Counter(l)
	ans = 1
	u = []
	for (i, j) in k.items():
		ans = ans * i
		u.append(j)
	max1 = 0
	for i in range(len(u)):
		if max1 < u[i]:
			max1 = u[i]
	if int(math.log(max1, 2)) == math.log(max1, 2):
		val = int(math.log(max1, 2))
	else:
		val = int(math.log(max1, 2)) + 1
	if len(set(u)) == 1 and u[0] & u[0] - 1 == 0:
		print(str(ans) + ' ' + str(val))
	else:
		print(str(ans) + ' ' + str(val + 1))


import sys
import math
input = sys.stdin.readline

def primeFactors(n):
	l = [0] * (n + 1)
	while n % 2 == 0:
		l[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l[i] += 1
			n = n / i
	if n > 2:
		l[int(n)] += 1
	return l
n = int(input())
if n == 1:
	print(1, 0)
else:
	l = primeFactors(n)
	maxi = 0
	for i in range(2, n + 1, 1):
		if l[i] > maxi:
			maxi = l[i]
	u = math.ceil(math.log(maxi, 2))
	ans = 0
	for i in range(2, n + 1, 1):
		if l[i] != 0:
			if 2 ** u != l[i]:
				ans += 1
				break
	mini = 1
	for i in range(2, n + 1):
		if l[i] != 0:
			mini = mini * i
	print(mini, ans + u)


from collections import defaultdict
from math import log2, ceil
n = int(input())
if n == 1:
	print(1, 0)
	exit()
d = defaultdict(int)
while n % 2 == 0:
	d[2] += 1
	n //= 2
ind = 3
while ind <= int(n ** 0.5) + 1:
	while n % ind == 0:
		d[ind] += 1
		n //= ind
	ind += 2
if n != 1:
	d[n] += 1
ma = -1
ans = 1
arr = []
for x in d:
	ma = max(ma, d[x])
	arr += [d[x]]
	ans *= x
if arr.count(ma) == len(arr) and 2 ** 30 % ma == 0:
	print(ans, ceil(log2(ma)))
else:
	print(ans, 1 + ceil(log2(ma)))


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())
(small, tmp, d) = (1, n, 2)
while tmp > 1:
	if tmp % d == 0:
		small *= d
		while tmp % d == 0:
			tmp //= d
	d += 1
(tmp, k) = (small, 0)
while tmp % n > 0:
	tmp *= tmp
	k += 1
if tmp > n:
	k += 1
print(small, k)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return list(map(str, input().strip()))

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby
from itertools import permutations as comb

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	return l
n = I()
l = primeFactors(n)
d = Counter(l)
s = set(l)
tmp = 1
ans = 1
for i in s:
	ans *= i
	tmp = max(tmp, d[i])
tmp = math.ceil(math.log(tmp, 2))
q = 0
for i in s:
	if d[i] != 2 ** tmp:
		tmp += 1
		break
print(ans, tmp)


import math

def is_prime(val):
	i = 3
	if val == 2:
		return True
	if val % 2 == 0:
		return False
	while i * i <= val:
		if val % i == 0:
			return False
		i += 2
	return True

def main():
	n = int(input())
	if n == 1:
		print(1, 0)
		return
	divs = []
	powers = []
	for i in range(2, 1001):
		if is_prime(i) and n % i == 0:
			cnt = 0
			while n % i == 0:
				cnt += 1
				n //= i
			divs.append(i)
			powers.append(cnt)
		if n == 1:
			break
	if n != 1:
		divs.append(n)
		powers.append(1)
	max_power = max(powers)
	square_roots = int(math.log(max_power, 2))
	smallest = 1
	for i in divs:
		smallest *= i
	if all((x == powers[0] for x in powers)):
		if powers[0] == 1:
			print(smallest, 0)
			return
		if 2 ** square_roots == max_power:
			print(smallest, square_roots)
			return
	if 2 ** square_roots != max_power:
		square_roots += 1
	square_roots += 1
	print(smallest, square_roots)
main()


import math
n = int(input())
arr = []
for i in range(2, n + 1):
	if n % i == 0:
		cnt = 0
		while n % i == 0:
			cnt += 1
			n = n // i
		arr.append([i, cnt])
mul = 0
mn = 1
st = 0
for i in range(len(arr)):
	mn = mn * arr[i][0]
	xx = int(math.log2(arr[i][1]))
	if arr[i][1] > 1 << xx:
		xx += 1
	st = max(st, xx)
for i in range(len(arr)):
	if arr[i][1] < 1 << st:
		mul = 1
print(mn, st + mul)


from math import log, ceil
n = int(input())
if n == 1:
	print(1, 0)
	exit()
f = {}
i = 2
while i <= n:
	if n % i == 0:
		f[i] = 0
		while n % i == 0:
			n = n // i
			f[i] += 1
	i += 1
ans = 1
for fi in f:
	ans = ans * fi
pow2 = {1 << i for i in range(1, 21)}
fvalues = set(f.values())
if fvalues == {1}:
	print(ans, 0)
elif len(fvalues) == 1:
	v = fvalues.pop()
	if v in pow2:
		print(ans, ceil(log(v, 2)))
	else:
		print(ans, ceil(log(v, 2)) + 1)
else:
	v = max(fvalues)
	print(ans, ceil(log(v, 2)) + 1)


from functools import reduce
import operator

def b():
	(primes, powers, counter) = ([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, 1009], [1, 2, 4, 8, 16, 32, 64], [0] * 169)
	stored = n = int(input())
	for p in range(len(primes)):
		while n % primes[p] == 0:
			(n, counter[p]) = (n // primes[p], counter[p] + 1)
	if n != 1:
		primes.append(n)
		counter.append(1)
	m = max(counter)
	if m < 2:
		return str(stored) + ' 0'
	else:
		minval = reduce(operator.mul, [primes[p] for p in range(len(primes)) if counter[p] != 0])
		p = count = 0
		while powers[p] < m:
			p += 1
		count = p + 1 if len([c for c in counter if c > 0 and c < powers[p]]) > 0 else p
		return str(minval) + ' ' + str(count)
print(b())


import math

def lcm(a, b):
	import math
	return a * b // math.gcd(a, b)

def solve():
	n = int(input())
	if n == 1:
		print(1, 0)
		return 0
	nCopy = n
	divs = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			divs.append(i)
			while n % i == 0:
				n //= i
		i += 1
	if n > 1:
		divs.append(n)
	b = divs[0]
	for i in range(1, len(divs)):
		b = lcm(b, divs[i])
	now = b
	n = nCopy
	steps = 0
	while now < n or now % n != 0:
		now *= now
		steps += 1
	if now != n:
		steps += 1
	print(b, steps)
solve()


import math
n = int(input())
if n == 1:
	print(1, 0)
else:
	factors = []
	for i in range(1, round(n ** 0.5) + 2):
		if n % i == 0:
			factors += [i, n // i]
	factors = list(set(factors))

	def isprime(n):
		if n == 1:
			return False
		if n < 4:
			return True
		for i in range(2, round(n ** 0.5) + 2):
			if n % i == 0:
				return False
		return True
	primes = []
	for factor in factors:
		if isprime(factor):
			primes.append(factor)
	exps = []
	for prime in primes:
		x = prime
		expo = 0
		while n % x == 0:
			x *= prime
			expo += 1
		exps.append(expo)
	b = max(exps)
	decs = math.ceil(math.log2(b))
	cheat = True
	exp = 2 ** decs
	for guy in exps:
		if guy != exp:
			cheat = False
			break
	prod = 1
	for guy in primes:
		prod *= guy
	if cheat:
		print(prod, decs)
	else:
		print(prod, decs + 1)


import sys

def rint():
	return map(int, sys.stdin.readline().split())

def find_div(n):
	i = 2
	divs = dict()
	while i * i <= n:
		cnt = 0
		while n % i == 0:
			cnt += 1
			n //= i
		if cnt:
			divs[i] = cnt
		i += 1
	if n != 1:
		divs[n] = 1
	return divs
n = int(input())
if n == 1:
	print(1, 0)
	exit()
div_dict = find_div(n)
max_cnt = max(div_dict.values())
mul_cnt = 1
if len(set(div_dict.values())) == 1 and max_cnt & max_cnt - 1 == 0:
	mul_cnt = 0
ans = 1
for i in div_dict:
	ans *= i
root_cnt = max_cnt.bit_length()
if max_cnt & max_cnt - 1 == 0:
	root_cnt -= 1
print(ans, root_cnt + mul_cnt)


import math
from collections import Counter
lis = []
nearest_pow_2 = []

def convert(n):
	start = 1
	while start < n:
		start *= 2
	return start

def primeFactors(n):
	while n % 2 == 0:
		lis.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			lis.append(i)
			n = n / i
	if n > 2:
		lis.append(n)
inp = int(input())
if inp == 1:
	print(1, 0)
else:
	primeFactors(inp)
	cur_lis = Counter(lis)
	key = list(cur_lis.keys())
	flag = 0
	for i in key:
		x = convert(cur_lis[i])
		if x > cur_lis[i]:
			flag = 1
		nearest_pow_2.append(x)
	m = 0
	for i in range(len(key)):
		m = max(m, math.log(nearest_pow_2[i], 2))
	x = list(set(lis))
	ans = 1
	for i in x:
		ans *= i
	m = int(m)
	nearest_pow_2.sort()
	if flag == 1 or nearest_pow_2[0] != nearest_pow_2[-1]:
		m += 1
	ans = int(ans)
	print(ans, m)


import math

def prime(k):
	if k == 1:
		return False
	w = int(math.sqrt(k)) + 1
	for i in range(2, w):
		if k % i == 0:
			return False
	return True

def div(n):
	ans = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				if prime(i):
					ans.append(i)
			else:
				if prime(i):
					ans.append(i)
				if prime(n // i):
					ans.append(n // i)
		i += 1
	return ans
t = int(input())
if t == 1:
	print(1, 0)
else:
	d = dict()
	q = div(t)
	for i in range(len(q)):
		while t % q[i] == 0 and t > 1:
			if q[i] in d:
				d[q[i]] += 1
			else:
				d[q[i]] = 1
			t = t // q[i]
	val = max(d.values())
	ans = 1
	for i in d.keys():
		ans *= i
	if val & val - 1 == 0:
		val2 = int(math.log(val, 2))
	else:
		val2 = int(math.log(val, 2)) + 1
	if len(set(d.values())) == 1 and val & val - 1 == 0:
		print(ans, val2)
	else:
		print(ans, val2 + 1)


from collections import Counter
import math

def primeFactors(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			a.append(i)
			n //= i
	if n > 2:
		a.append(n)
	return Counter(a)
n = int(input())
out = 0
if n == 1:
	print(n, out)
else:
	a = primeFactors(n)
	s = 1
	for i in a:
		s *= i
	v = list(a.values())
	gcd = v[0]
	for i in v[1:]:
		gcd = math.gcd(gcd, i)
	p = 0
	while gcd % 2 == 0:
		p += 1
		gcd //= 2
	out += p
	nv = max(v) // pow(2, p)
	if nv != 1:
		out += 1
	nvm = math.ceil(math.log2(nv))
	out += nvm
	print(s, out)


import math
pf = {}
n = int(input())
if n == 1:
	print('1 0')
	exit()
care = 0
while True:
	done = True
	for i in range(2, n):
		if n % i == 0:
			while n % i == 0:
				n /= i
				n = int(n)
				pf[i] = pf.get(i, 0) + 1
				care = max(care, pf[i])
			done = False
			break
	if done:
		if n != 1:
			pf[n] = pf.get(n, 0) + 1
		break
two = 1
two_count = 0
while True:
	if two >= care:
		break
	two *= 2
	two_count += 1
ans = 0
for x in pf.items():
	if x[1] != two:
		ans = 1
		break
first_ans = 1
for x in pf.items():
	first_ans *= x[0]
print(f'{first_ans} {ans + two_count}')


n = int(input())
if n == 1:
	print(1, 0)
else:
	r = round(n ** 0.5) + 1
	plist = [False, True] * ((n >> 1) + 1)
	(plist[1], plist[2]) = (False, True)
	for i in range(3, r, 2):
		if plist[i]:
			for j in range(i * i, n, i):
				plist[j] = False
	prime = [i for i in range(n) if plist[i]]
	pro = 1
	freq = []
	for i in prime:
		count = 0
		if n % i == 0:
			pro *= i
			while n % i == 0:
				n //= i
				count += 1
			freq.append(count)
	if len(freq) == 0:
		print(n, 0)
	else:
		m = max(freq)
		(c, k) = (2, 1)
		while c < m:
			c = c << 1
			k += 1
		if set(freq) == {1} or set(freq) == {1, 0}:
			print(pro, 0)
		elif set(freq) == {c, 0} or set(freq) == {c}:
			print(pro, k)
		else:
			print(pro, k + 1)


def primfacs(n):
	i = 2
	primfac = []
	while i * i <= n:
		while n % i == 0:
			primfac.append(i)
			n = n / i
		i = i + 1
	if n > 1:
		primfac.append(n)
	return primfac
n = int(input())
l = primfacs(n)
d = {}
t = []
k = 1
while 2 ** k < 10 ** 9:
	t.append(2 ** k)
	k = k + 1
for i in range(len(l)):
	if l[i] not in d:
		d[l[i]] = 0
for i in range(len(l)):
	d[l[i]] += 1
smax = 0
for i in d:
	if d[i] > smax:
		smax = d[i]
k = 0
fl = True
for i in d:
	if d[i] != smax:
		k = 1
		fl = False
		break
if smax not in t:
	i = 0
	while smax > t[i]:
		i += 1
	smax = t[i]
	if fl:
		k = k + 1
while smax > 1:
	smax = smax // 2
	k = k + 1
s = 1
for i in d:
	s = s * i
if int(s) == n:
	print(int(s), 0)
else:
	print(int(s), k)


my = 1000001
s = [i for i in range(my)]

def sieve():
	s[1] = 1
	for i in range(2, my):
		if s[i] == i:
			for j in range(i * i, my, i):
				if s[j] == j:
					s[j] = i

def factor(n):
	r = {}
	p = 1
	while n != 1:
		if s[n] not in r:
			r[s[n]] = 0
			p *= s[n]
		r[s[n]] += 1
		n = int(n / s[n])
	print(p, end=' ')
	return r.values()
sieve()
x = factor(int(input()))
c = 0
if len(x) == 0:
	print(0)
else:
	mx = max(x)
	if mx == 1:
		print(0)
	else:
		m = len(bin(mx - 1)) - 2
		for i in x:
			if i != 1 << m:
				c = 1
				break
		print(m + c)


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 tp(n):
	k = 1
	while k < n:
		k *= 2
	return k
n = int(input())
a = []
z = 1
if n == 1:
	exit(print(1, 0))
for i in range(2, int(n ** 0.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)


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)


from collections import Counter
import functools
import operator
import sys
n = int(input())
num = n
c = Counter()
if n == 1:
	print('1 0')
	sys.exit()
for i in range(2, n + 1):
	if i > n:
		break
	freq = 0
	while n % i == 0:
		c[i] += 1
		n //= i
min_product = functools.reduce(operator.mul, c.keys(), 1)
if min_product == num:
	print('{} 0'.format(num))
	sys.exit()
most_common = c.most_common()[0][1]
all_same = c.most_common()[0][1] == c.most_common()[-1][1]

def is_pow2(val):
	if val == 1:
		return True
	if val % 2 == 1:
		return False
	return is_pow2(val // 2)

def count2(val):
	if val == 1:
		return 0
	times = 0
	while val != 1:
		val //= 2
		times += 1
	return times
if not is_pow2(most_common):
	num_ops = 2 + count2(most_common)
elif all_same:
	num_ops = count2(most_common)
else:
	num_ops = 1 + count2(most_common)
print('{} {}'.format(min_product, num_ops))


import math
N = int(input())
if N == 1:
	print(1, end=' ')
	print(0)
	exit()
dic = {}
while N != 1:
	z = int(math.sqrt(N))
	for i in range(2, z + 1):
		if N % i == 0:
			dic[i] = dic.get(i, 0) + 1
			N = N // i
			break
	else:
		dic[N] = dic.get(N, 0) + 1
		N = 1
output1 = 1
output2 = 0
max1 = 0
count = 0
for i in dic:
	output1 *= i
	max1 = max(max1, dic[i])
if math.log(max1, 2) == int(math.log(max1, 2)):
	matchwith = max1
	x = math.log(matchwith, 2)
else:
	x = math.ceil(math.log(max1, 2))
	matchwith = 2 ** x
for i in dic:
	if dic[i] != matchwith:
		output2 += 1
		break
print(output1, end=' ')
print(int(x + output2))


import math
num = int(input())

def nextPow2(n):
	res = 1
	i = 0
	while res < n:
		res <<= 1
		i += 1
	return (res, i)

def numMoves(n):
	factorization = dict()
	i = 2
	k = n
	while k > 1:
		if k % i == 0:
			if i not in factorization:
				factorization[i] = 0
			factorization[i] += 1
			k //= i
		else:
			i += 1
	highest = 0
	res = 1
	for factor in factorization:
		highest = max(highest, factorization[factor])
		res *= factor
	(maxPow, i) = nextPow2(highest)
	for factor in factorization:
		if factorization[factor] != maxPow:
			return (res, i + 1)
	return (res, i)
(res, i) = numMoves(num)
print(res, i)


import math
n = int(input())

def PrimeList(limit):
	Plist = []
	for i in range(2, limit + 1):
		divcheck = False
		for j in Plist:
			if j * j > i:
				break
			if i % j == 0:
				divcheck = True
				break
		if divcheck == False:
			Plist.append(i)
	return Plist
T = PrimeList(10 ** 3)
D = {}
for i in T:
	while n % i == 0:
		if i in D:
			D[i] += 1
		else:
			D[i] = 1
		n = int(n / i)
if n > 1:
	D[n] = 1
if len(D) == 0:
	print(n, 0)
else:
	P = 1
	for i in D:
		P *= i
	L = [i for i in D.values()]
	ma = max(L)
	mi = min(L)
	l = int(math.log(ma, 2))
	if ma == 2 ** l:
		if mi == ma:
			print(P, l)
		else:
			print(P, l + 1)
	else:
		print(P, l + 2)


import sys
from math import *

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

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

def mints():
	return 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)


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)
	exit()
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
maxpower = natlog(setres.most_common(1)[0][1])
maxnum = 2 ** maxpower
cnt_actions = maxpower
for (j, p) in setres.items():
	if p < maxnum:
		cnt_actions += 1
		break
print(res, cnt_actions)


import math
import sys
x = int(input())
if x == 1:
	print(1, 0)
	sys.exit()
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 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)


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 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)


import math
l = []

def primeFactors(n):
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(int(n))
n = int(input())
primeFactors(n)
s = list(set(l))
mul = 1
ma = 0
if n == 1:
	print(1, 0)
	exit()
for i in s:
	c = l.count(i)
	ma = max(ma, c)
	mul = mul * i
c = 0
while 2 ** c < ma:
	c += 1
fl = 0
for i in s:
	if l.count(i) != 2 ** c:
		fl = 1
if fl == 1:
	c = c + 1
print(mul, c)


from math import log
from math import ceil
A = int(input())
a = A
m = []
i = 2

def Z(x):
	return round(x) == x
b = round(a ** 0.5 + 1)
while i <= b:
	if a % i == 0:
		m += [[i, 0]]
	while a % i == 0:
		m[-1][1] += 1
		a //= i
	i += 1
if a != 1:
	m += [[a, 1]]
f = True
i = 0
while i < len(m):
	if m[i][1] != 1:
		f = False
	i += 1
if f:
	print(A, 0)
else:
	t = True
	p = 1
	i = 0
	while i < len(m):
		p *= m[i][0]
		i += 1
	print(p, end=' ')
	f = Z(log(m[0][1], 2))
	if f:
		i = 1
		while i < len(m):
			if m[i][1] != m[0][1]:
				f = False
			i += 1
		if f:
			print(round(log(m[0][1], 2)))
			t = False
	if t:
		maxm1 = max(m, key=lambda x: x[1])[1]
		print(1 + ceil(log(maxm1, 2)))


li2 = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912]
from functools import reduce
from collections import defaultdict
from math import floor, sqrt
from bisect import bisect
n = int(input())
m = n
if n == 1:
	print(1, 0)
else:
	d = defaultdict(int)
	for i in range(2, floor(sqrt(n)) + 1):
		while n % i == 0:
			d[i] += 1
			n //= i
	if n > 1:
		d[n] += 1
	vl = list(d.values())
	v = max(vl)
	f = 1
	if len(set(vl)) == 1 and v in li2:
		f = 0
	if v == 1:
		print(m, 0)
	else:
		kl = list(d.keys())
		p = reduce(lambda x, y: x * y, kl)
		i = bisect(li2, v)
		if li2[i - 1] == v:
			print(p, i - 1 + f)
		else:
			print(p, i + f)


import sys
import math
n = int(input())
if n <= 2:
	print(n, 0)
	sys.exit()
list = []
t = 0

def check(y, maxim):
	return int(math.pow(2, maxim) - y)
for i in range(2, n + 1):
	if n % i == 0:
		while n % i == 0:
			n /= i
			list.append(i)
list1 = []
for i in list:
	if list1.count(i) == 0:
		list1.append(i)
count = []
m = 0
for i in list1:
	count.append(list.count(i))
	m += 1
ma = max(count)
l = math.log(ma, 2)
t = 0
if l - int(l) == 0:
	l = int(l)
else:
	l = int(l) + 1
b = False
for i in range(0, m):
	for j in range(0, check(count[i], l)):
		list.append(list1[i])
		b = True
p = 1
if b == True:
	t += 1
for i in list:
	p *= i
while math.sqrt(p) - int(math.sqrt(p)) == 0:
	p = math.sqrt(p)
	t += 1
print(int(p), t)


import math
n = int(input())
(factors, mmax, mmin) = (1, 1, float('inf'))
factor = 2
while n != 1:
	cur = 0
	flag = False
	while n % factor == 0:
		n = n // factor
		cur += 1
		flag = True
	if flag:
		factors *= factor
		mmin = min(mmin, cur)
	mmax = max(mmax, cur)
	factor += 1
mmin = min(mmin, mmax)
i = 0
while math.pow(2, i) < mmax:
	i += 1
if mmax != math.pow(2, i) or mmin != math.pow(2, i):
	i += 1
print(factors, i)


from sys import stdin, stdout
import cProfile, math
from collections import Counter
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10000000)

class Operation:

	def __init__(self, name, function, function_on_equal, neutral_value=0):
		self.name = name
		self.f = function
		self.f_on_equal = function_on_equal

def add_multiple(x, count):
	return x * count

def min_multiple(x, count):
	return x

def max_multiple(x, count):
	return x
sum_operation = Operation('sum', sum, add_multiple, 0)
min_operation = Operation('min', min, min_multiple, 1000000000.0)
max_operation = Operation('max', max, max_multiple, -1000000000.0)

class SegmentTree:

	def __init__(self, array, operations=[sum_operation, min_operation, max_operation]):
		self.array = array
		if type(operations) != list:
			raise TypeError('operations must be a list')
		self.operations = {}
		for op in operations:
			self.operations[op.name] = op
		self.root = SegmentTreeNode(0, len(array) - 1, self)

	def query(self, start, end, operation_name):
		if self.operations.get(operation_name) == None:
			raise Exception('This operation is not available')
		return self.root._query(start, end, self.operations[operation_name])

	def summary(self):
		return self.root.values

	def update(self, position, value):
		self.root._update(position, value)

	def update_range(self, start, end, value):
		self.root._update_range(start, end, value)

	def __repr__(self):
		return self.root.__repr__()

class SegmentTreeNode:

	def __init__(self, start, end, segment_tree):
		self.range = (start, end)
		self.parent_tree = segment_tree
		self.range_value = None
		self.values = {}
		self.left = None
		self.right = None
		if start == end:
			self._sync()
			return
		self.left = SegmentTreeNode(start, start + (end - start) // 2, segment_tree)
		self.right = SegmentTreeNode(start + (end - start) // 2 + 1, end, segment_tree)
		self._sync()

	def _query(self, start, end, operation):
		if end < self.range[0] or start > self.range[1]:
			return None
		if start <= self.range[0] and self.range[1] <= end:
			return self.values[operation.name]
		self._push()
		left_res = self.left._query(start, end, operation) if self.left else None
		right_res = self.right._query(start, end, operation) if self.right else None
		if left_res is None:
			return right_res
		if right_res is None:
			return left_res
		return operation.f([left_res, right_res])

	def _update(self, position, value):
		if position < self.range[0] or position > self.range[1]:
			return
		if position == self.range[0] and self.range[1] == position:
			self.parent_tree.array[position] = value
			self._sync()
			return
		self._push()
		self.left._update(position, value)
		self.right._update(position, value)
		self._sync()

	def _update_range(self, start, end, value):
		if end < self.range[0] or start > self.range[1]:
			return
		if start <= self.range[0] and self.range[1] <= end:
			self.range_value = value
			self._sync()
			return
		self._push()
		self.left._update_range(start, end, value)
		self.right._update_range(start, end, value)
		self._sync()

	def _sync(self):
		if self.range[0] == self.range[1]:
			for op in self.parent_tree.operations.values():
				current_value = self.parent_tree.array[self.range[0]]
				if self.range_value is not None:
					current_value = self.range_value
				self.values[op.name] = op.f([current_value])
		else:
			for op in self.parent_tree.operations.values():
				result = op.f([self.left.values[op.name], self.right.values[op.name]])
				if self.range_value is not None:
					bound_length = self.range[1] - self.range[0] + 1
					result = op.f_on_equal(self.range_value, bound_length)
				self.values[op.name] = result

	def _push(self):
		if self.range_value is None:
			return
		if self.left:
			self.left.range_value = self.range_value
			self.right.range_value = self.range_value
			self.left._sync()
			self.right._sync()
			self.range_value = None

	def __repr__(self):
		ans = '({}, {}): {}\n'.format(self.range[0], self.range[1], self.values)
		if self.left:
			ans += self.left.__repr__()
		if self.right:
			ans += self.right.__repr__()
		return ans

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def primeFactors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def isprime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def test_print(*args):
	if test:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result
TestCases = False
test = False

def main():
	n = get_int()
	factors = primeFactors(n)
	if n == 1:
		print(1, 0)
		return
	ma = max(factors.values())
	times = math.ceil(math.log2(ma))
	r = 1
	for i in factors.keys():
		r = r * i
	vals = list(factors.values())
	a = vals[0]
	for i in vals:
		if i != a or math.log2(i) % 1 != 0:
			times += 1
			break
	print(r, times)
if TestCases:
	for _ in range(get_int()):
		cProfile.run('main()') if test else main()
else:
	cProfile.run('main()') if test else main()


from operator import itemgetter
n = int(input())
ans = []
cnt = 2
steps = [1]
for i in range(60):
	steps.append(steps[-1] * 2)
tmp = 0
if n == 1:
	print(1, 0)
	exit()
while n != 1:
	if n % cnt == 0:
		n //= cnt
		tmp += 1
	else:
		if tmp != 0:
			ans.append([tmp, cnt])
		tmp = 0
		cnt += 1
if tmp != 0:
	ans.append([tmp, cnt])
ans.sort(key=itemgetter(0), reverse=True)
g = 1
for i in range(len(ans)):
	g *= ans[i][1]
if ans[0][0] not in steps:
	i = 0
	while ans[0][0] > steps[i]:
		i += 1
	print(g, i + 1)
else:
	i = 0
	de = 0
	while ans[0][0] > steps[i]:
		i += 1
	mb = True
	de = i
	for i in range(len(ans)):
		if ans[i][0] != ans[0][0]:
			mb = False
	if mb:
		print(g, de)
	else:
		print(g, de + 1)


n = int(input())
i = 2
s = {}
if n == 1:
	print(1, 0)
	exit()
while n > 1:
	if n % i == 0:
		if i in s:
			s[i] += 1
		else:
			s[i] = 1
		n //= i
	else:
		i += 1
ans = 0
maxp2 = max([s[i] for i in s])
k = 1
while k < maxp2:
	k <<= 1
	ans += 1
if len(list(filter(lambda x: x < k, [s[i] for i in s]))) > 0:
	ans += 1
ans1 = 1
for i in s:
	ans1 *= i
print(ans1, ans)


from collections import Counter
n = int(input())
p = 2
fact = Counter()
while p ** 2 <= n:
	if n % p:
		p += 1
	else:
		fact[p] += 1
		n //= p
fact[n] += 1
res1 = 1
res2 = 1
do_mul = 1
for p in fact.keys():
	exp = fact[p]
	if exp != 1:
		log = exp.bit_length()
		tpl = 2 ** log
		while tpl > exp:
			tpl //= 2
			log -= 1
		while tpl < exp:
			tpl *= 2
			log += 1
		if tpl > exp:
			do_mul = 2
		res2a = log + 1
	else:
		res2a = 1
	if res1 == 1:
		res2 = res2a
	elif res2a > res2:
		res2 = res2a
		do_mul = 2
	elif res2a < res2:
		do_mul = 2
	res1 *= p
res2 += do_mul
res2 -= 1
if res2 == 1:
	print(res1, '0')
else:
	print(res1, res2 - 1)


def prime_factors(a):
	if a == 1:
		return (1, 0)
	factors = {}
	i = 2
	orig = a
	while i <= int(orig ** 0.5) + 1:
		while a % i == 0:
			a = a // i
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
		i += 1
	if a > 1:
		factors[a] = 1
	if sorted(factors)[-1] == orig:
		return (N, 0)
	multiple = 1
	for i in factors:
		multiple *= i
	if orig == multiple ** 2:
		return (int(orig ** 0.5), 1)
	elif orig == multiple:
		return (orig, 0)
	something = sorted([factors[i] for i in factors])
	counter = 0
	while 2 ** counter < something[-1]:
		counter += 1
	if all([x == something[0] for x in something]) and something[0] & something[0] - 1 == 0:
		return (multiple, counter)
	return (multiple, counter + 1)
N = int(input())
print(*prime_factors(N))


import sys
from math import floor, ceil, sqrt, gcd
input = sys.stdin.readline
n = int(input())
factors = {}
orign = n
i = 2
while i * i <= n:
	if n % i == 0:
		if i not in factors.keys():
			factors[i] = 0
		factors[i] += 1
		n /= i
	else:
		i += 1
if n > 1:
	if n not in factors.keys():
		factors[int(n)] = 0
	factors[int(n)] += 1
ans = 0
if len(factors.keys()) == 0:
	print(str(orign) + ' 0')
else:
	for key in factors.keys():
		ans = max(ans, factors[key])
	n = 1
	for key in factors.keys():
		n *= key
	nextPowBits = (ans - 1).bit_length()
	nextPow = 2 ** nextPowBits
	if ans == 1:
		print(str(int(n)) + ' ' + '0')
	else:
		done = True
		for key in factors.keys():
			if factors[key] != nextPow:
				done = False
				break
		if done:
			print(str(int(n)) + ' ' + str((ans - 1).bit_length()))
		else:
			print(str(int(n)) + ' ' + str((ans - 1).bit_length() + 1))


from math import sqrt

def resolve(x):
	fatores = fatoraInt(x)
	contOperacao = 0
	minimo = 1
	cont = 0
	for i in fatores:
		minimo = minimo * i[0]
		if i[1] == 1:
			cont = cont + 1
	if cont == len(fatores):
		return (minimo, contOperacao)
	else:
		maximo = fatores[0][1]
		flag = 0
		for i in fatores[1:]:
			if i[1] != maximo:
				flag = 1
			if i[1] > maximo:
				maximo = i[1]
		if maximo % 2 == 0 and flag == 1:
			(k, p) = expo(maximo)
			contOperacao = 1 + k
		elif flag == 1:
			(k, p) = expo(maximo + 1)
			contOperacao = 1 + k
		else:
			(k, p) = expo(maximo)
			contOperacao = k
			if not p:
				contOperacao = contOperacao + 1
	return (minimo, contOperacao)

def expo(n):
	cont = 0
	x = 1
	while x < n:
		x = x * 2
		cont = cont + 1
	if x == n:
		return (cont, True)
	else:
		return (cont, False)

def fatoraInt(x):
	fatores = []
	cont = 0
	aux = x
	while x % 2 == 0:
		x = x / 2
		cont = cont + 1
	if cont != 0:
		fatores.append([2, cont])
	cont = 0
	for i in range(3, int(sqrt(aux)) + 2, 2):
		cont = 0
		if x % i == 0 and isPrimo(i):
			while x % i == 0:
				cont = cont + 1
				x = x / i
			fatores.append([i, cont])
	if int(x) != 1:
		fatores.append([int(x), 1])
	return fatores

def isPrimo(p):
	if p == 2:
		return True
	elif p % 2 == 0:
		return False
	else:
		for i in range(3, int(sqrt(p)) + 2, 2):
			if p % i == 0:
				return false
		return True
n = int(input())
(minimo, contOp) = resolve(n)
print(str(minimo) + ' ' + str(contOp))


import math

def B1062(n):
	initial_value = n
	dictionary = dict()
	if n == 1:
		print(n, 0)
		return
	value = 1
	while n % 2 == 0:
		dictionary[2] = 1 + dictionary.get(2, 0)
		n = n / 2
		value = 2
	for prime in range(3, int(math.sqrt(n)) + 1, 2):
		found_prime = False
		while n % prime == 0:
			dictionary[prime] = dictionary.get(prime, 0) + 1
			n = n / prime
			if not found_prime:
				value *= prime
				found_prime = True
	if n > 2:
		dictionary[n] = dictionary.get(n, 0) + 1
		value *= n
	steps = 0
	max_power = max(dictionary.values())
	math_log = math.log(max_power, 2)
	if max_power == 1:
		print(initial_value, 0)
		return
	if all((x == max_power for x in dictionary.values())) and math.log(max_power, 2) == int(math.log(max_power, 2)):
		steps = int(math_log)
	elif int(math_log) == math_log:
		steps = int(math_log) + 1
	else:
		steps = int(math_log) + 1 + 1
	print(' '.join([str(int(value)), str(steps)]))
B1062(int(input()))


from sys import stdin, stdout
from math import ceil, log2
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))

def factors(n):
	while n & 1 == 0:
		mp[2] = mp.get(2, 0) + 1
		n //= 2
	for f in range(3, n + 1, 2):
		while n % f == 0:
			mp[f] = mp.get(f, 0) + 1
			n //= f
	if n > 2:
		mp[n] = 1
for _ in range(1):
	mp = {}
	n = nmbr()
	factors(n)
	ans = 1
	op = 0
	mx = 0
	if n == 1:
		print(1, 0)
		continue
	for (f, p) in mp.items():
		mx = max(mx, p)
		ans *= f
	op = ceil(log2(mx))
	for (k, v) in mp.items():
		if v != 2 ** op:
			op += 1
			break
	print(ans, op)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout

def primeFactors(n):
	pf = []
	while n % 2 == 0:
		pf.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			pf.append(int(i))
			n = n / i
	if n > 2:
		pf.append(int(n))
	return pf

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for _ in range(1):
		n = ri()
		op1 = 0
		op2 = 0
		z = 1
		while True:
			pf = primeFactors(n)
			if len(set(pf)) == len(pf):
				break
			d = Counter(pf)
			x = 1
			c = 0
			for i in d:
				if d[i] % 2:
					c = 1
					x *= i
			if c == 1:
				n *= x
				op1 += 1
			n = int(math.sqrt(n))
			op2 += 1
			z *= x
		op = min(op1, 1) + op2
		print(n, op)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


def inint():
	return int(input())

def inlist():
	return list(map(int, input().split()))

def pf(a):
	factor = []
	i = 2
	while i * i <= a:
		ch = 0
		while a % i == 0:
			ch += 1
			a //= i
		if ch != 0:
			factor.append([i, ch])
		i += 1
	if a > 1:
		factor.append([a, 1])
	return factor

def main():
	n = inint()
	f = pf(n)
	sol = 1
	mxp = 0
	for (i, j) in f:
		mxp = max(mxp, j)
	from math import log, ceil
	ans = 0
	if mxp > 0:
		ans = ceil(log(mxp, 2))
	for (i, j) in f:
		if j < 2 ** ans:
			ans += 1
			break
	for (i, j) in f:
		sol *= i
	print(sol, ans)
main()


n = int(input())
if n == 1:
	print(n, 0)
	exit()
import math

def primefac(n):
	pf = []
	while not n % 2:
		n //= 2
		pf.append(2)
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while not n % i:
			n //= i
			pf.append(i)
	if n > 2:
		pf.append(n)
	return pf
pf = primefac(n)
if len(pf) == 1:
	print(n, 0)
	exit()
occ = {}
for i in pf:
	occ[i] = occ.get(i, 0) + 1
mulflag = False
mx = 0
mn = 10 ** 9
for i in occ:
	mx = max(mx, occ[i])
	mn = min(mn, occ[i])
pf2 = list(set(pf))
prod = 1
for i in pf2:
	prod *= i
mx = 2 ** math.ceil(math.log(mx, 2))
if mn != mx:
	mulflag = True
m = prod
res = int(math.log(mx, 2))
if mulflag:
	res += 1
print(m, res)


n = int(input())
t = n
n_ans = 1
i = 2
while i <= n:
	if n % i == 0:
		n_ans *= i
	while n % i == 0:
		n //= i
	i += 1
cnt = 0
tmp = n_ans
while tmp % t != 0:
	cnt += 1
	tmp *= tmp
if tmp != t:
	cnt += 1
print(n_ans, cnt)


n = int(input())
ans = 1
cnt = 0
k = n
for i in range(2, n + 1):
	if n % i == 0:
		ans *= i
		while n % i == 0:
			n //= i
rec = ans
while rec % k > 0:
	rec *= rec
	cnt += 1
if rec > k:
	cnt += 1
print(ans, cnt)


from sys import stdin
n = int(stdin.readline().strip())
if n == 1:
	print(1, 0)
	exit(0)
v = [[]]
N = 10 ** 25 + 1
for i in range(2, (n + 2) // 2):
	x = i ** 0.5
	if x != int(x):
		v.append([])
		x = i
		while x <= N:
			v[-1].append(x)
			x *= x
ans = 0
aux = n ** 0.5
while aux == int(aux):
	ans += 1
	n = int(aux)
	aux = n ** 0.5
t = False
for i in v:
	for j in i:
		if j % n == 0:
			if j != n:
				ans += 1
			t = True
			break
	if t:
		break
if t:
	aux = j ** 0.5
	while aux == int(aux):
		ans += 1
		j = int(aux)
		aux = j ** 0.5
else:
	j = n
print(int(j), ans)


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)


from math import ceil, log
d = dict()

def pf(n):
	i = 2
	while i * i <= n:
		while n % i == 0:
			d[i] = d.get(i, 0) + 1
			n = n // i
		i += 1
	if n != 1:
		d[n] = d.get(n, 0) + 1
n = int(input())
if n == 1:
	print(1, 0)
else:
	pf(n)
	m = max(d.values())
	steps = 0
	flag = False
	for i in d.values():
		if i != m:
			steps += 1
			flag = True
			break
	x = log(m, 2)
	if flag or x.is_integer():
		steps += ceil(x)
	else:
		steps += ceil(x) + 1
	ans = 1
	for i in d.keys():
		ans = ans * i
	print(ans, steps)


import math

def Prime(n):
	d = [1]
	while n % 2 == 0:
		d.append(2)
		n //= 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d.append(i)
			n //= i
	if n > 2:
		d.append(n)
	return d
n = int(input())
d = Prime(n)
d.sort()
c = [1]
ans = c[0]
for i in range(1, len(d)):
	if d[i] == d[i - 1]:
		c[-1] += 1
	else:
		ans *= d[i]
		c.append(1)
f = 1
if len(set(c[1:])) == 1:
	f = 0
for i in range(len(c)):
	if math.ceil(math.log2(c[i])) != math.floor(math.log2(c[i])):
		f = 1
	if c[i] == 1 and i != 0:
		c[i] = 1
		f = 1
	else:
		c[i] = math.ceil(math.log2(c[i]))
if ans == n:
	nn = 0
else:
	nn = max(c) + f
print(ans, nn)


from collections import defaultdict
n = int(input())
if n == 1:
	print(1, 0)
else:
	l = [2]
	count = 1
	for j in range(l[-1] + 1, 1000 + 1):
		for k in range(count):
			if j % l[k] == 0:
				break
			if k == count - 1:
				l.append(j)
				count += 1
				break
	d = defaultdict(int)
	x = n
	check = False
	for t in l:
		if t <= x:
			while x % t == 0:
				check = True
				x = x / t
				d[t] += 1
		else:
			break
	if x != 1:
		d[int(x)] = 1
	if not check:
		print(n, 0)
	if check:
		max_pow = d[max(d, key=lambda x: d[x])]
		min_pow = d[min(d, key=lambda x: d[x])]
		if max_pow == 1:
			print(n, 0)
		else:
			minn = 32
			for i in [2, 4, 8, 16, 32]:
				if i - max_pow >= 0 and minn > i - max_pow:
					minn = i - max_pow
					mark = i
			result = 1
			for m in d:
				result = result * m
			if minn == 0 and min_pow == max_pow:
				print(result, [2, 4, 8, 16, 32].index(mark) + 1)
			else:
				print(result, 1 + ([2, 4, 8, 16, 32].index(mark) + 1))


from math import log2, trunc, ceil
n = int(input())
d = {}
i = 2
x = n
max_p = 1
while i ** 2 <= x:
	if n % i == 0:
		d[i] = 0
		while n % i == 0:
			d[i] += 1
			n //= i
			max_p = max(max_p, d[i])
	i += 1
if n > 1:
	d[n] = 1
	max_p = max(max_p, d[n])
m = 1
equal = True
for key in d.keys():
	m *= key
	if d[key] != max_p:
		equal = False
if equal:
	if trunc(log2(max_p)) == log2(max_p):
		print(m, int(log2(max_p)))
	else:
		print(m, int(ceil(log2(max_p))) + 1)
else:
	print(m, int(ceil(log2(max_p))) + 1)


def mainA():
	n = int(input())
	a = [0] + [int(e) for e in input().split()] + [1001]
	(ans, mx) = (0, 0)
	for i in range(1, n + 1):
		if a[i] == a[i - 1] + 1 and a[i] == a[i + 1] - 1:
			ans += 1
			mx = max(mx, ans)
		else:
			ans = 0
	print(mx)

def mainB():

	def isFrom2(x):
		i = 1
		cnt = 0
		while i < x:
			i <<= 1
			cnt += 1
		return (cnt, i != x)
	n = int(input())
	i = 2
	map = dict()
	while i * i <= n:
		if n % i == 0:
			map[i] = 0
			while n % i == 0:
				map[i] += 1
				n //= i
		i += 1
	if n != 1:
		map[n] = 1
	(ans, b, f, m) = (1, 0, False, 0)
	for (key, value) in map.items():
		ans *= key
		ret = isFrom2(value)
		if not f:
			f |= ret[1]
			if m != 0 and m != value:
				f = True
			m = value
		b = max(b, ret[0])
	print(ans, b + (1 if f else 0))
mainB()


from collections import defaultdict as dif
dic = dif(lambda : 0)
x = int(input())
if x == 1:
	print(1, 0)
	exit(0)
while x % 2 == 0:
	dic[2] += 1
	x //= 2
mx = dic[2]
n = 3
while n * n <= x:
	while x % n == 0:
		dic[n] += 1
		x //= n
	mx = max(mx, dic[n])
	n += 2
if x > 1:
	dic[x] = 1
	mx = max(1, mx)
from math import log2, ceil
lg = ceil(log2(mx))
mxt = 1 << lg
nm = 1
stp = 0
for n in dic:
	if dic[n] != mxt and dic[n]:
		stp = 1
		break
for n in dic:
	if dic[n]:
		nm *= n
stp += lg
print(nm, stp)


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)
	mx = max(fctr)
	next_pow2 = 2 ** ceil(log(mx) / log(2))
	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())))


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
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)


n = int(input())
n2 = n
flag = 0
i = 0
ans = 1
flag2 = 0
ans2 = 0
for i in range(2, int(n ** 0.5) + 1):
	if n % i == 0:
		ans *= i
	num = 0
	while n % i == 0:
		n //= i
		num += 1
	num2 = 0
	num3 = bin(num)[3:]
	flag = 0
	for j in num3:
		if j == '1':
			flag = 1
			break
	if flag == 1 or num == 1:
		num2 = len(num3) + 1
		flag2 = 1
	else:
		num2 = len(num3)
	if num2 != ans2 and ans2 != 0 and (num2 != 0):
		flag2 = 1
	ans2 = max(ans2, num2)
	if n < i:
		break
num3 = ans * n
if num3 == n2:
	print(num3, 0)
else:
	if n != 1:
		num2 = 2
		flag2 = 1
	else:
		num2 = 1
	print(num3, max(ans2 + flag2, num2))


n = eval(input())
a = []
flag = [True] * 1000001
for i in range(2, 1000001):
	if flag[i]:
		a.append(i)
		for j in range(i + i, 1000001, i):
			flag[j] = False
if flag[n]:
	print(n, 0)
	exit(0)
b = []
ans = 1
for i in range(len(a)):
	if n % a[i] == 0:
		ans = ans * a[i]
		for j in range(1, 30):
			if n % a[i] ** j != 0:
				b.append(j - 1)
				n = n / a[i] ** (j - 1)
				break
	if n == 0:
		break
b = sorted(b)
temp = b[-1]
kle = 0
for i in range(31):
	k = 1
	k = k << i
	if k >= temp:
		if k != temp or b[0] != b[-1]:
			kle = 1
		kle = i + kle
		break
print(ans, kle)


n = int(input())
m = n
d = 2
A = []
if n != 1:
	while d * d <= n:
		if n % d == 0:
			A.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		A.append(n)
	D = dict()
	p = 1
	for i in range(len(A)):
		if A[i] not in D.keys():
			D[A[i]] = 1
			p *= A[i]
		else:
			D[A[i]] += 1
	s_max = max(D.values())
	k = 1
	for i in range(50):
		if k >= s_max:
			break
		k *= 2
	for q in D.values():
		if q != k:
			i += 1
			break
else:
	p = 1
	i = 0
if p == m:
	i = 0
print(p, i)


import math

def issame(arr, m):
	for i in range(len(arr)):
		if arr[i] != m:
			return False
	return True

def ispower(m):
	if m % 2 == 0:
		m = int(m / 2)
		while m % 2 == 0:
			m = m / 2
		if m != 1:
			return False
		else:
			return True
	return False

def SOE(n):
	p = 2
	global ps
	primes = [True for i in range(n + 1)]
	primes[0] = False
	primes[1] = False
	while p <= n ** 0.5:
		cur = p
		cur = cur + p
		while cur <= n:
			primes[cur] = False
			cur = cur + p
		p = p + 1
		while not primes[p]:
			p = p + 1
	ps = [i for i in range(len(primes)) if primes[i]]
	global pset
	pset = set(ps)

def fact(n):
	val = ps[0]
	bs = []
	fs = []
	ct = 0
	if n in pset:
		return (n, 0)
	while n > 1:
		if n % val == 0:
			a = 1
			n = int(n / val)
			bs.append(val)
			while n % val == 0:
				n = n / val
				a = a + 1
			fs.append(a)
		ct = ct + 1
		val = ps[ct]
	m = max(fs)
	p = 1
	for val in bs:
		p = p * val
	if m == 1:
		return (p, 0)
	if issame(fs, m):
		if ispower(m):
			num = int(math.log2(m))
		else:
			num = int(math.log2(m)) + 1
			num = num + 1
	else:
		if ispower(m):
			num = int(math.log2(m))
		else:
			num = int(math.log2(m)) + 1
		num = num + 1
	return (p, num)

def main():
	n = int(input())
	if n == 1:
		print(str(1) + ' ' + str(0))
		return None
	SOE(n)
	(p, ct) = fact(n)
	print(str(p) + ' ' + str(ct))
main()


from sys import stdin
n = int(stdin.readline().strip())
if n == 1:
	print(1, 0)
	exit(0)
ans = 0
aux = n ** 0.5
while aux == int(aux):
	n = aux
	ans += 1
	aux = n ** 0.5
n = int(n)
sieve = []
vis = [False for i in range(n + 1)]
for i in range(2, n + 1):
	if not vis[i]:
		sieve.append(i)
		for j in range(i, n + 1, i):
			vis[j] = True
arr = []
y = 1
n1 = n
for i in sieve:
	if n % i == 0:
		x = 0
		while n % i == 0:
			n //= i
			x += 1
		y *= i
n = n1
x = y
while y % n != 0:
	y *= y
	ans += 1
if y != n:
	ans += 1
print(x, ans)


import math

def isSquare(n):
	if math.ceil(math.sqrt(n)) == math.floor(math.sqrt(n)):
		return 1
	else:
		return 0

def squareDiv(n):
	c = 0
	for i in range(2, n):
		if n % i == 0:
			c = isSquare(i)
		if c == 1:
			return n / i
	return 1
c = 0
n = input()
n = int(n)
temp = n
if n == 1:
	print(str(n) + ' ' + str(c))
else:
	while True:
		if isSquare(n) == 1:
			n = int(math.sqrt(n))
			continue
		p = n
		n = n * squareDiv(n)
		if p == n:
			break
	print(str(n) + ' ', end='')
	while True:
		if n == temp:
			c = c - 1
			break
		if n % temp == 0:
			break
		c = c + 1
		n = n * n
	print(c + 1)


import math
from collections import defaultdict
import functools
primes = [2]
N = 1001

def generate_primes():
	for i in range(2, N):
		isPrime = True
		sqr = math.ceil(math.sqrt(i))
		for p in primes:
			if i % p == 0:
				isPrime = False
				break
			if p > sqr:
				break
		if isPrime:
			primes.append(i)

def find_factors(n):
	prime_counter = 0
	prime_dict = defaultdict(int)
	while n > 1 and prime_counter < len(primes):
		while n > 1 and n % primes[prime_counter] == 0:
			n = n // primes[prime_counter]
			prime_dict[primes[prime_counter]] += 1
		prime_counter += 1
	if n > 1:
		prime_dict[n] += 1
	return prime_dict

def get_num_steps(arr):

	def find_power(mx):
		two_power = 1
		i = 0
		while two_power < mx:
			two_power *= 2
			i += 1
		return (i, two_power == mx)
	mx = arr[0]
	all_equal = True
	for i in range(1, len(arr)):
		mx = max(mx, arr[i])
		if arr[i] != arr[i - 1]:
			all_equal = False
	(pw, pw_equal) = find_power(mx)
	if all_equal and pw_equal:
		return pw
	return pw + 1

def solution(n):
	generate_primes()
	prime_dict = find_factors(n)
	max_power = get_num_steps(list(prime_dict.values()))
	return (functools.reduce(lambda x, y: x * y, prime_dict.keys(), 1), max_power)
n = int(input())
if n == 1:
	print(1, 0)
else:
	print(*solution(n))


import math
n = int(input())

def is_prime(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return i
	return None

def prime_factors(n):
	l = []
	while True:
		i = is_prime(n)
		if i == None:
			l.append(n)
			break
		l.append(i)
		n = int(n / i)
	return l
l = prime_factors(n)
m = []
for i in l:
	if i not in m:
		m.append(i)
s = [0 for j in range(len(m))]
for i in l:
	for j in range(len(m)):
		if m[j] == i:
			s[j] += 1
a = 1
for i in m:
	a *= i
ma = max(s)
n = 1
r = 0
while n < ma:
	n *= 2
	r += 1
if all((i == s[0] for i in s)) and n == ma:
	r -= 1
print(a, r + 1)


import math
n = int(input())

def is_sqr(n):
	a = int(n ** 0.5)
	return a * a == n

def factors(n):
	if n == 1:
		return ([(1, 1)], 0)
	p = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			tot = 0
			while n % i == 0:
				n //= i
				tot += 1
			p.append((i, tot))
		i += 1
	if n != 1:
		p.append((n, 1))
	ret = 1
	for i in p:
		if i[1] % 2 == 1:
			ret *= i[0]
	return (p, ret)
(p, ret) = factors(n)
maxu = max([i[1] for i in p])
i = 1
tot = 0
while i < maxu:
	i += i
	tot += 1
extra = 0
for j in p:
	if j[1] != i:
		extra = 1
minim = 1
for j in p:
	minim *= j[0]
print(minim, tot + extra)


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)


n = int(input())
from math import sqrt as S
from math import log as log, ceil as upar
d = {}
c = 0
for i in range(2, int(S(n)) + 1):
	if n % i == 0:
		while n % i == 0:
			c += 1
			n = n // i
		d[i] = c
		c = 0
if n > 1:
	d[n] = 1
ans = 1
for i in d.keys():
	ans *= i
print(ans, end=' ')
father_pow = 0
for i in d.keys():
	u = upar(log(d[i]) / log(2))
	father_pow = max(father_pow, u)
if all((d[i] == 2 ** father_pow for i in d.keys())):
	print(father_pow)
else:
	print(father_pow + 1)


from sys import stdin
import math

def find_prime(n):
	num = n
	prime_factors = [0] * (num + 1)
	while n % 2 == 0:
		prime_factors[2] += 1
		n = n // 2
	for i in range(3, num + 1, 2):
		while n % i == 0:
			n = n // i
			prime_factors[i] += 1
	return (prime_factors, n)

def check_prime(number):
	if number > 2:
		return True
	else:
		return False

def check_all_equal(prime_factors):
	i = 2
	equal = 0
	while i < len(prime_factors):
		if prime_factors[i] != 0:
			equal = prime_factors[i]
			break
		i += 1
	while i < len(prime_factors):
		if prime_factors[i] != 0:
			if prime_factors[i] != equal:
				return False
		i += 1
	return True

def find_nearest_2_power(num, steps):
	power = 0
	while 2 ** power < num:
		power += 1
	steps += power
	if 2 ** power == num:
		return (steps, 0)
	else:
		return (steps + 1, 1)

def print_the_number(prime_factors, steps):
	product = 1
	for i in range(2, len(prime_factors)):
		if prime_factors[i] != 0:
			product = product * i
	print(product, steps)
n = int(stdin.readline().strip())
(prime_factors, modified) = find_prime(n)
if n == 1:
	print(1, 0)
else:
	steps = 0
	if check_all_equal(prime_factors):
		maxfactor = max(prime_factors)
		(steps, c) = find_nearest_2_power(maxfactor, steps)
		print_the_number(prime_factors, steps)
	else:
		steps += 1
		maxfactor = max(prime_factors)
		(steps, c) = find_nearest_2_power(maxfactor, steps)
		if c == 1:
			steps -= 1
		print_the_number(prime_factors, steps)


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		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())
(N,) = getIntList()
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)


from math import log2, sqrt

def main():
	n = int(input())
	d = {}
	cur = n
	for i in range(2, int(sqrt(n)) + 2):
		while cur % i == 0:
			t = d.get(i, 0) + 1
			d[i] = t
			cur //= i
	if cur != 1:
		d[cur] = 1
	if d == {} or max(d.values()) == 1:
		return print(n, 0)
	cur = []
	action = False
	for k in d:
		q = log2(d[k])
		if q - int(q) != 0 or q == 0:
			if not action:
				action = True
			cur.append(int(q) + 1)
		else:
			cur.append(int(q))
	ans_2 = max(cur)
	if action or len(set(cur)) != 1:
		ans_2 += 1
	ans_1 = 1
	for k in d:
		ans_1 *= k
	return print(ans_1, ans_2)
main()


def yakusuu(i, m):
	_i = i
	while i ** 2 <= m:
		if m % i == 0:
			return i
		else:
			i += 1
	for j in range(_i - 1, 0, -1):
		if m % j == 0:
			break
	return m // j

def factoring(N):
	i = 2
	original_N = N
	result = {}
	judge = -1
	tmp = 2
	while tmp <= N and (tmp - 1) ** 2 <= original_N:
		tmp = yakusuu(tmp, N)
		if judge == tmp:
			result[tmp] += 1
		else:
			result[tmp] = 1
		N //= tmp
		judge = tmp
	return result
n = int(input())
if n == 1:
	print('1 0')
else:
	result = factoring(n)
	va = list(result.values())
	ke = list(result.keys())
	ma = va[0]
	ans = 1
	flag = True
	for i in range(len(ke)):
		if va[i] > ma:
			ma = va[i]
			flag = False
		if va[i] < ma:
			flag = False
		ans *= ke[i]
	if ma == 1:
		print('{} {}'.format(ans, 0))
	else:
		i = 0
		while 2 ** i < ma:
			i += 1
		if 2 ** i != ma or not flag:
			print('{} {}'.format(ans, 1 + i))
		else:
			print('{} {}'.format(ans, i))


from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()

def getPrimes(x):
	primes = {}
	while ~x & 1:
		primes[2] = primes.get(2, 0) + 1
		x //= 2
	for i in range(3, int(math.sqrt(x)) + 2, 2):
		while x % i == 0:
			primes[i] = primes.get(i, 0) + 1
			x //= i
	if x != 1:
		primes[x] = 1
	return primes
if n == 1:
	print(1, 0)
else:
	(ans, cnt) = (1, 0)
	primes = getPrimes(n)
	maxP = 0
	minP = inf
	ans = 1
	for k in primes:
		maxP = max(maxP, primes[k])
		minP = min(minP, primes[k])
		ans *= k
	cnt = math.ceil(math.log2(maxP))
	if maxP == minP and maxP != 2 ** cnt or maxP != minP:
		cnt += 1
	print(ans, cnt)


from sys import stdin, stdout
from math import sin, tan, cos, pi, atan2, sqrt, acos, atan, factorial
n = int(stdin.readline())
mp = {}
d = 2
while d * d <= n:
	while n % d == 0:
		if d not in mp:
			mp[d] = 1
		else:
			mp[d] += 1
		n //= d
	d += 1
if n != 1:
	mp[n] = 1
ans = 1
cnt = 1
s = set()
for v in mp:
	ans *= v
	cnt = max(cnt, mp[v])
	s.add(mp[v])
for i in range(20):
	if 1 << i == cnt and len(s) <= 1:
		stdout.write(str(ans) + ' ' + str(i) + '\n')
		break
	if 1 << i >= cnt:
		stdout.write(str(ans) + ' ' + str(1 + i) + '\n')
		break


__author__ = 'tanunia'
from sys import stdin
import math
n = int(stdin.readline())
nums = {}
end = int(math.sqrt(n))
total_n = n
for i in range(2, end + 1):
	while total_n % i == 0:
		if i not in nums:
			nums[i] = 0
		nums[i] += 1
		total_n /= i
if total_n > 1:
	nums[total_n] = 1
max_pow = 0
ans1 = 1
for k in nums.keys():
	ans1 *= k
	if nums[k] > max_pow:
		max_pow = nums[k]
pow2 = 1
cnt = 0
while pow2 < max_pow:
	pow2 *= 2
	cnt += 1
ans2 = cnt
for k in nums.keys():
	if nums[k] < pow2:
		ans2 += 1
		break
print(str(int(ans1)) + ' ' + str(ans2))


import math
from math import log
number = int(input())
list = []

def fun(n):
	while n > 1:
		for i in range(2, n + 1):
			if n % i == 0:
				n = n // i
				list.append(i)
				break
if number != 1:
	fun(number)
	dic = {}
	q = []
	for i in list:
		dic[i] = list.count(i)
		q.append(dic[i])
	s = set(list)
	w = 1
	for i in s:
		w = w * i
	e = math.ceil(log(max(q), 2))
	if len(set(q)) == 1 and e == int(log(max(q), 2)):
		print(w, e)
	else:
		print(w, e + 1)
else:
	print(1, 0)


import math

def primeFactors(n):
	if n % 2 == 0:
		dict1[2] = 0
	while n % 2 == 0:
		dict1[2] += 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			dict1[i] = 0
		while n % i == 0:
			dict1[i] += 1
			n = n // i
	if n > 2:
		dict1[n] = 0
		dict1[n] += 1
n = int(input())
if n == 1:
	print(1, 0)
else:
	dict1 = {}
	primeFactors(n)
	max1 = 1
	lst = []
	for i in dict1:
		lst.append(dict1[i])
	if max(lst) == min(lst) and max(lst) == 1:
		print(n, 0)
	elif max(lst) == min(lst):
		prod = 1
		for i in dict1:
			prod *= i
		str1 = bin(max(lst))
		str2 = str1[2:]
		list1 = list(str2)
		if list1.count('0') == len(list1) - 1:
			print(prod, math.ceil(math.log2(max(lst))))
		else:
			print(prod, math.ceil(math.log2(max(lst))) + 1)
	else:
		prod = 1
		for i in dict1:
			prod *= i
		print(prod, math.ceil(math.log2(max(lst))) + 1)


x = n = int(input())
p = [0] * 1000001
if n == 1:
	print(1, 0)
	exit(0)
k = 0
for i in range(2, 1000001):
	while x % i == 0:
		x //= i
		p[i] += 1
	k = max(k, p[i])
b = int.bit_length(k) - 1
if k != 1 << b:
	b += 1
	k = 1 << b
m = 1
q = 0
ans = b
for i in range(2, 1000001):
	if p[i] > 0:
		if p[i] != k:
			q = 1
		m *= i
print(m, ans + q)


import sys
import os
import math
import copy
from math import gcd
from bisect import bisect
from io import BytesIO, IOBase
from math import sqrt, floor, factorial, gcd, log, ceil
from collections import deque, Counter, defaultdict
from itertools import permutations, combinations
import itertools

def Int():
	return int(sys.stdin.readline())

def Mint():
	return map(int, sys.stdin.readline().split())

def Lstr():
	return list(sys.stdin.readline().strip())

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

def Mstr():
	return map(str, sys.stdin.readline().strip().split())

def List():
	return list(map(int, sys.stdin.readline().split()))

def Hash():
	return dict()

def Mod():
	return 1000000007

def Ncr(n, r, p):
	return fact[n] * (ifact[r] * ifact[n - r] % p) % p

def Most_frequent(list):
	return max(set(list), key=list.count)

def Mat2x2(n):
	return [List() for _ in range(n)]

def Lcm(x, y):
	return x * y // gcd(x, y)

def dtob(n):
	return bin(n).replace('0b', '')

def btod(n):
	return int(n, 2)

def common(l1, l2):
	return set(l1).intersection(l2)

def solution():
	n = Int()
	s = 0
	c = 0
	while int(n ** 0.5) == n ** 0.5 and n > 1:
		n = n ** 0.5
		s += 1
	for i in range(int(n ** 0.5), 1, -1):
		while n % (i * i) == 0:
			n = n // i
			s += 1
			c = 1
	print(int(n), s + c)
solution()


import math

def pr(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			a.append(int(i))
			n = n / i
	if n > 2:
		a.append(int(n))
	return list(a)
from collections import defaultdict
a = int(input())
if a == 1:
	print(1, 0)
else:
	b = pr(a)
	c = defaultdict(int)
	for i in range(len(b)):
		c[b[i]] += 1
	d = []
	for i in c:
		d.append([c[i], i])
	d = max(d)[0]
	e = 0
	while 1 > 0:
		if 2 ** e >= d:
			break
		else:
			e += 1
	f = 0
	for i in c:
		if c[i] != 2 ** e:
			f = 1
	c = 1
	d = list(set(b))
	for i in range(len(d)):
		c = c * d[i]
	print(c, f + e)


from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
n = ii()
m = {}
res = 1
n1 = n
for i in range(2, int(sqrt(n)) + 1):
	m[i] = 0
	while n % i == 0:
		n //= i
		m[i] += 1
	if m[i] > 0:
		res *= i
if n > 1:
	m[n] = 1
	res *= n
x = 0
for i in m.keys():
	x = max(x, m[i])
res1 = pow(res, x)
f = res
c = 0
while f < res1:
	f *= f
	c += 1
if f != n1:
	c += 1
print(res, c)


import math

def primeFactors(n):
	dic = {}
	while n % 2 == 0:
		if 2 in dic:
			dic[2] += 1
		else:
			dic[2] = 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
			n = n / i
	if n > 2:
		if n in dic:
			dic[n] += 1
		else:
			dic[n] = 1
	return dic
n = int(input())
arr = primeFactors(n)
arr2 = []
for key in arr:
	arr2.append(arr[key])
length = len(arr2)
ans = 0
while True:
	sqrt = True
	if len(arr2) == 0:
		break
	for i in arr2:
		if i % 2 == 1:
			sqrt = False
			break
	if sqrt:
		ans += 1
		for i in range(length):
			arr2[i] = arr2[i] / 2
	else:
		break
p = 0
start = 1
if len(arr2) == 0:
	a = 1
else:
	a = max(arr2)
for i in range(1000):
	if start < a:
		start *= 2
		p += 1
	else:
		break
plus1 = False
for i in range(length):
	if arr2[i] < start:
		plus1 = True
		break
if plus1:
	ans += p + 1
else:
	ans += p
ans0 = 1
for i in arr:
	ans0 *= i
print(int(ans0), ans)


n = int(input())
if n == 1:
	from sys import exit
	print(1, 0)
	exit()
(d, k, mx, result) = ({}, 2, 0, 1)
while n > 1:
	x = 1000000000
	for i in range(k, n + 1):
		if n % i == 0:
			d[i] = 0
			x = i
			break
	while n % x == 0:
		n = n // x
		d[x] += 1
	k = x + 1
	result *= x
	mx = max(mx, d[x])
(res, item) = (0, 1)
while item < mx:
	item *= 2
	res += 1
if item == mx:
	ans = 0
	for (i, x) in enumerate(d):
		if d[x] != mx:
			break
		ans += 1
	if ans < len(d):
		res += 1
else:
	res += 1
print(result, res)


import sys

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7

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

def iinp():
	return int(input())

def nninp():
	return map(int, sys.stdin.readline().strip().split())

def llinp():
	return list(map(int, sys.stdin.readline().strip().split()))

def p(xyz):
	print(xyz)

def p2(a, b):
	print(a, b)
import math

def primeFactor(n):
	l = [0] * (n + 1)
	while n % 2 == 0:
		l[1] += 1
		n = n // 2
	for i in range(3, n + 2, 2):
		while n % i == 0:
			l[i - 1] += 1
			n = n // i
	return l
n = iinp()
l = primeFactor(n)
if sum(l) == 1 or n == 1:
	print(n, 0)
else:
	ans1 = 0
	x = max(l)
	nos = 0
	while x > 2 ** nos:
		nos += 1
	for c in l:
		if c < 2 ** nos and c != 0:
			ans1 += 1
			break
	ans1 += nos
	ans2 = 0
	for i in range(len(l)):
		if l[i] != 0 and ans2 == 0:
			ans2 = i + 1
		elif l[i] != 0:
			ans2 = ans2 * (i + 1)
	print(ans2, ans1)


import math
n = int(input())

def prime_factors(n):
	i = 2
	factors = {}
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors[i] = factors[i] + 1 if i in factors.keys() else 1
	if n > 1:
		factors[n] = factors[n] + 1 if n in factors.keys() else 1
	return factors
factors = prime_factors(n)
tmp = 1
for (key, val) in factors.items():
	tmp *= key ** val
all_shisuu_is_one = True
for shisuu in factors.values():
	if shisuu != 1:
		all_shisuu_is_one = False
		break
if not all_shisuu_is_one:
	first = True
	all_shisuu_same_kaijo = True
	for shisuu in factors.values():
		if first:
			first_shisuu = shisuu
			tmp = math.log(first_shisuu, 2)
			if int(tmp) != tmp:
				all_shisuu_same_kaijo = False
				break
			first = False
		elif first_shisuu != shisuu:
			all_shisuu_same_kaijo = False
			break
if all_shisuu_is_one:
	count = 0
	out_val = n
else:
	if all_shisuu_same_kaijo:
		count = 0
	else:
		count = 1
	log_shisuu_list = [math.ceil(math.log(shisuu, 2)) for shisuu in factors.values()]
	max_log_shisuu = max(log_shisuu_list)
	count += max_log_shisuu
	out_val = 1
	for prime in factors.keys():
		out_val *= prime
print('%d %d' % (out_val, count))


import math

def primeFactorize(n):
	dic = {}
	i = 2
	while n > 1:
		while n % i == 0:
			try:
				dic[i] += 1
			except:
				dic[i] = 1
			n = n // i
		i += 1
	return dic

def noofoperation(lis):
	temp = max(lis)
	z = math.ceil(math.log(temp, 2))
	y = 2 ** z
	t = False
	for i in lis:
		if i != y:
			t = True
			break
	if t:
		return z + 1
	else:
		return z
n = int(input())
if n == 1:
	print(1, 0)
	exit()
count = 0
dic = primeFactorize(n)
count = noofoperation(list(dic.values()))
pro = 1
for i in dic:
	pro *= i
print(pro, count)


def sieveOfEratosthenes(N, s):
	prime = [False] * (N + 1)
	for i in range(2, N + 1, 2):
		s[i] = 2
	for i in range(3, N + 1, 2):
		if prime[i] == False:
			s[i] = i
			for j in range(i, int(N / i) + 1, 2):
				if prime[i * j] == False:
					prime[i * j] = True
					s[i * j] = i

def nextPowerOf2(n):
	p = 1
	if n and (not n & n - 1):
		return n
	while p < n:
		p <<= 1
	return p

def generatePrimeFactors(N):
	if N == 1:
		return {1: 1}
	data = dict()
	s = [0] * (N + 1)
	sieveOfEratosthenes(N, s)
	curr = s[N]
	cnt = 1
	while N > 1:
		N //= s[N]
		if curr == s[N]:
			cnt += 1
			continue
		data[curr] = cnt
		curr = s[N]
		cnt = 1
	return data
N = int(input())
data = generatePrimeFactors(N)
mina = 1
powers = []
flag = 1
for i in data:
	mina *= i
	powers.append(data[i])
m = max(powers)
c = 1
next2 = nextPowerOf2(m)
if next2 == m and powers.count(m) == len(powers):
	c = 0
try:
	print(mina, c + generatePrimeFactors(next2)[2])
except:
	print(N, 0)


import math
from sys import exit
from collections import defaultdict
n = int(input())
d = defaultdict(lambda : 0)
if n == 1:
	print(1, 0)
	exit()
while n % 2 == 0:
	d[2] += 1
	n //= 2
for i in range(3, int(math.sqrt(n)) + 1):
	while n % i == 0:
		n //= i
		d[i] += 1
	if n == 1:
		break
if n > 1:
	d[n] += 1
m = 1
for e in d:
	m *= e
a = [e for e in d.values()]
if len(set(a)) == 1 and math.log(a[0], 2).is_integer():
	print(m, int(math.log(a[0], 2)))
else:
	t = max(a)
	print(m, math.ceil(math.log(t, 2)) + 1)


import math
N = 10 ** 6 + 5
spf = [-1] * (N + 1)
for i in range(N + 1):
	spf[i] = i
for i in range(2, int(math.sqrt(N)) + 1):
	if spf[i] == i:
		for j in range(i * 2, N + 1, i):
			if spf[j] == j:
				spf[j] = i

def factorize(n):
	d = {}
	while n != 1:
		p = spf[n]
		if p in d:
			d[p] += 1
		else:
			d[p] = 1
		n //= p
	return d
table = [0] * 31
table[0] = 1
for i in range(1, 31):
	table[i] = table[i - 1] * 2
import bisect
n = int(input())
d = factorize(n)
ans = 1
for k in d.keys():
	ans *= k
cnt = 0
while True:
	cnt1 = 0
	cnt_e = 0
	max_v = 0
	for (k, v) in d.items():
		if v == 1:
			cnt1 += 1
		if v % 2 == 0:
			cnt_e += 1
		max_v = max(max_v, v)
	if cnt1 == len(d):
		break
	if cnt_e == len(d):
		for (k, v) in d.items():
			d[k] = v // 2
		cnt += 1
	else:
		j = bisect.bisect_left(table, max_v)
		b = table[j]
		for k in d.keys():
			d[k] = b
		cnt += 1
print(ans, cnt)


import sys
import os
from io import BytesIO, IOBase
from time import time
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def lcm(x, y):
	return x * y / gcd(x, y)

def fact(x, mod=mod):
	ans = 1
	for i in range(1, x + 1):
		ans = ans * i % mod
	return ans

def arr2D(n, m, default=0):
	return [[default for j in range(m)] for i in range(n)]

def arr3D(n, m, r, default=0):
	return [[[default for k in range(r)] for j in range(m)] for i in range(n)]

def sortDictV(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

class DSU:

	def __init__(self, length):
		self.length = length
		self.parent = [-1] * self.length

	def getParent(self, node, start):
		if node >= self.length:
			return False
		if self.parent[node] < 0:
			if start != node:
				self.parent[start] = node
			return node
		return self.getParent(self.parent[node], start)

	def union(self, node1, node2):
		parent1 = self.getParent(node1, node1)
		parent2 = self.getParent(node2, node2)
		if parent1 == parent2:
			return False
		elif self.parent[parent1] <= self.parent[parent2]:
			self.parent[parent1] += self.parent[parent2]
			self.parent[parent2] = parent1
		else:
			self.parent[parent2] += self.parent[parent1]
			self.parent[parent1] = parent2
		return True

	def getCount(self, node):
		return -self.parent[self.getParent(node, node)]

def exact(num):
	if abs(num - round(num)) <= 10 ** (-9):
		return round(num)
	return num
import math

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n / i
	if n > 2:
		factors.append(n)
	return factors

def solve(n):
	if n == 1:
		print(1, 0)
		return
	factors = primeFactors(n)
	times = []
	factMap = {}
	for i in factors:
		if factMap.get(i) == None:
			factMap[i] = 1
		else:
			factMap[i] += 1
	maxx = 0
	for i in factMap:
		maxx = max(maxx, factMap[i])
	minn = 1
	for i in factMap:
		minn *= i
	if maxx % 2:
		maxx += 1
	times = math.ceil(math.log2(maxx))
	add = 1
	if minn ** 2 ** times == n:
		add = 0
	if minn == n:
		print(int(minn), 0)
	else:
		print(int(minn), math.ceil(math.log2(maxx)) + add)
n = int(input())
solve(n)


import os, sys
from io import BytesIO, IOBase
from math import sqrt, ceil
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def dtb(n):
	return bin(n).replace('0b', '')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
t = sqrt(n)
d = dict()
i = 2
while i < n and i <= t:
	if n % i == 0:
		d[i] = d.get(i, 0)
		while n % i == 0:
			d[i] += 1
			n //= i
	i += 1
if n != 1:
	d[n] = d.get(n, 0) + 1
ans = 1
t = 0
t2 = 10 ** 10
tot = 0
l = 0
for i in d:
	ans *= i
	t = max(d[i], t)
	t2 = min(d[i], t2)
if t > 1:
	ck = dtb(t).lstrip('0')
	o = ck.count('1')
	if o > 1:
		tot += len(ck) + 1
		l = 1
	else:
		tot += len(ck) - 1
	if not l and t != t2:
		tot += 1
print(ans, tot)


n = int(input())

def pr(r, k=2):
	while k <= r:
		if r % k:
			k += 1
		else:
			r //= k
			yield k
k = list(pr(n))
p = 1
z = 0
y = 0
q = 1000000
for i in range(len(k)):
	g = k.count(k[i])
	if g >= p:
		p = g
	if g <= q:
		q = g
f = p
if q == 1000000:
	q = 1
while p != 1:
	if p % 2 != 0:
		p += 1
		y += 1
	else:
		p = p // 2
		z += 1
k = set(k)
k = list(k)
s = 1
for i in range(len(k)):
	s = s * int(k[i])
if y != 0 or q != f:
	print(s, z + 1)
else:
	print(s, z)


n = int(input())
m = n
ans = 1
num = 0
for i in range(2, m + 1):
	if n % i == 0:
		ans *= i
		while n % i == 0:
			n //= i
res = ans
while res % m > 0:
	res *= res
	num += 1
if res > m:
	num += 1
print(ans, num)


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())
a = 1
i = 2
k = 0
m = 0
ans = 0
if n == 1:
	m = 1
while n != 1:
	if n % i == 0:
		step = 0
		while n % i == 0:
			n //= i
			step += 1
		if m == 0:
			k = step
		m = max(m, step)
		if k != step:
			k = -1
		a *= i
	i += 1
i = 1
while m > i:
	i *= 2
	ans += 1
if k != -1 and m == i:
	print(a, ans)
else:
	print(a, ans + 1)


import math
import collections
n = int(input())
if n == 1:
	print(1, end=' ')
	print(0)
else:
	l = collections.defaultdict(lambda : 0)
	while n % 2 == 0:
		l[2] += 1
		n //= 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l[i] += 1
			n //= i
	if n > 2:
		l[n] += 1
	d = max(l.values())
	num = 1
	for t in set(l.keys()):
		num *= t
	ans = 0
	flag = False
	while d != 1:
		if d % 2 == 0:
			ans += 1
			d //= 2
		else:
			d += 1
			flag = True
	if len(set(l.values())) > 1 or flag:
		ans += 1
	print(num, end=' ')
	print(ans)


from math import log2, ceil
n = int(input())
divis = set()
i = 2
actions = 0
set_cnt = set()
n_copy = n
while i * i <= n:
	cnt = 0
	if n_copy % i == 0:
		divis.add(i)
	while n_copy % i == 0:
		n_copy //= i
		cnt += 1
	if cnt != 0:
		num = ceil(log2(cnt))
		set_cnt.add(cnt)
		actions = max(actions, num)
	i += 1
if n_copy > 1:
	divis.add(n_copy)
	actions = max(actions, 0)
	set_cnt.add(1)
ans = 1
for elem in divis:
	ans *= elem
if len(set_cnt) > 1 or (len(set_cnt) > 0 and list(set_cnt)[0] != 2 ** actions):
	actions += 1
print(ans, actions)


n = int(input())
x = n
k = 2
num = 1
m1 = 1
m2 = 100
while k * k <= x:
	count = 0
	while x % k == 0:
		count += 1
		x //= k
	if count > 0:
		num *= k
		m1 = max(m1, count)
		m2 = min(m2, count)
	k += 1
if x > 1:
	num *= x
	m2 = 1
s = bin(m1)[2:]
a = 1 if s.count('1') == 1 else -1
b = 0
if a == 1 and m1 != m2:
	b = 1
c = len(s)
m = c - a + b
if n == 1:
	m = 0
print(num, m)


from math import *
a = int(input())
p = []
b = a
prime = 1
for i in range(a + 5):
	p.append(0)
while a > 1:
	q = 0
	for z in range(2, floor(sqrt(a)) + 1):
		if a % z == 0:
			p[z] += 1
			a /= z
			prime = 0
			q = 1
			break
	if q == 0:
		p[int(a)] += 1
		break
q = 1
r = 1
t = 0
qw = 0
while q < max(p):
	q *= 2
	t += 1
for i in range(b + 5):
	if p[i] != 0:
		if p[i] < q:
			qw = 1
		r *= i
print(r, t + +qw)


import math

def is_power(n):
	return bin(n).count('1') == 1
n = int(input())
x = n
i = 2
factors = {}
if n > 1:
	while i <= int(math.sqrt(x)) + 1:
		if n % i:
			i += 1
		else:
			n //= i
			if i in factors.keys():
				factors[i] += 1
			else:
				factors[i] = 1
	if n > 1:
		factors[n] = 1
	result = 1
	for x in factors:
		result *= x
	value_max = max(factors.values())
	result_max = 0
	if value_max > min(factors.values()) or not is_power(value_max):
		result_max += 1
	if is_power(value_max):
		result_max += int(math.log2(value_max))
	else:
		result_max += int(math.log2(value_max)) + 1
	print(' '.join([str(result), str(result_max)]))
else:
	print(' '.join(['1', '0']))


def pf(x):
	i = 2
	ans = []
	while i * i <= x:
		while x % i == 0:
			ans.append(i)
			x = x / i
		i = i + 1
	if x > 1:
		ans.append(x)
	return ans
n = int(input())
if n == 1:
	print(1, 0)
	exit(0)
fc = pf(n)
values = []
dic = {}
num = 1
for i in fc:
	if i in dic:
		dic[i] += 1
	else:
		dic[i] = 1
for (key, value) in dic.items():
	num *= key
	values.append(value)
maxi = max(values)
if maxi == 1:
	print(n, 0)
else:
	for i in range(1, maxi + 1):
		if 2 ** i >= maxi:
			print(int(num), i + (1 if len(set(values)) > 1 or maxi < 2 ** i else 0))
			break


n = int(input())
if n == 1:
	print(1, 0)
	quit()
res = 1
t = n
L = []
for i in range(2, t + 1):
	if n % i == 0:
		res *= i
		c = 0
		while n % i == 0:
			n //= i
			c += 1
		if c > 0:
			L.append(c)
	if n == 1:
		break
l = len(L)
a = []
ma = 0
for i in range(l):
	c = 0
	k = L[i]
	while k:
		k //= 2
		c += 1
	if L[i] % 2 ** (c - 1) == 0:
		a.append(c - 1)
		ma = max(c - 1, ma)
	else:
		a.append(c)
		ma = max(c, ma)
if len(set(a)) == 1:
	f = 0
	for i in L:
		if i % 2 ** ma != 0:
			f = 1
			break
	if f:
		print(res, ma + 1)
	else:
		print(res, ma)
else:
	print(res, ma + 1)


def factorize(n):
	fct = []
	(b, e) = (2, 0)
	while b * b <= n:
		while n % b == 0:
			n = n // b
			e = e + 1
		if e > 0:
			fct.append((b, e))
		(b, e) = (b + 1, 0)
	if n > 1:
		fct.append((n, 1))
	return fct

def main():
	n = int(input())
	l = factorize(n)
	anscnt = 0
	ma = 0
	for i in range(len(l)):
		ma = max(ma, l[i][1])
	c = 0
	a = 1
	while True:
		if a >= ma:
			break
		a *= 2
		c += 1
	v = 1
	for i in range(len(l)):
		for j in range(a - l[i][1]):
			v *= l[i][0]
			anscnt = 1
	n *= v
	for i in range(c):
		n = n ** (1 / 2)
		anscnt += 1
	print(int(n), anscnt, sep=' ')
main()


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return l

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(''.join([str(x) for x in a]) + '\n')

def nextPowerOf2(n):
	k = 1
	while k < n:
		k = k << 1
	return k
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = 1
for _ in range(t):
	n = ii()
	if n == 1:
		print(1, 0)
		continue
	d = defaultdict(lambda : 0)
	l = primeFactors(n)
	for i in l:
		d[i] += 1
	l = list(d.keys())
	res = 0
	pw2 = 10000000000000
	for i in l:
		x = d[i]
		c = 0
		while x % 2 == 0:
			x //= 2
			c += 1
		pw2 = min(pw2, c)
	res = pw2
	for i in l:
		d[i] //= 2 ** pw2
	minans = 1
	mx = 0
	temp = 0
	for i in l:
		mx = max(mx, nextPowerOf2(d[i]))
		toAdd = mx - d[i]
		if toAdd > 0:
			temp = 1
		minans *= i
	for i in l:
		if d[i] == 1 and mx > 1:
			mx = max(mx, nextPowerOf2(d[i] + 1))
		toAdd = mx - d[i]
		if toAdd > 0:
			temp = 1
	if mx > 0:
		print(int(minans), int(res + log(mx, 2) + temp))
	else:
		print(int(minans), int(res + temp))


import configparser
import math
import sys
input = sys.stdin.readline

def main():
	n = int(input())
	if n == 1:
		print(1, 0)
		return
	max_n = int(math.sqrt(n)) + 5
	prime = [True for i in range(max_n)]
	for i in range(2, max_n):
		if prime[i]:
			for j in range(2 * i, max_n, i):
				prime[j] = False
	p_fac = {}
	for i in range(2, max_n):
		if i * i > n:
			break
		while n % i == 0:
			p_fac[i] = p_fac[i] + 1 if i in p_fac else 1
			n //= i
	if n != 1:
		p_fac[n] = 1
	min_ans = 1
	for i in p_fac.keys():
		min_ans *= i
	largest_num = max(p_fac.values())
	for i in range(100):
		if 2 ** i >= largest_num:
			break
	if len(list(filter(lambda x: x == 2 ** i, p_fac.values()))) != len(p_fac):
		print(min_ans, ' ', i + 1)
	else:
		print(min_ans, ' ', i)
main()


n = int(input())
mn = []
x = n
p = False
c = 0
f = 0
while n > 1:
	p = False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			mn.append(i)
			p = True
			n //= i
			break
	if not p:
		mn.append(n)
		n = 1
d = {}
for i in mn:
	d[i] = 0
for i in mn:
	d[i] += 1
while True:
	p = True
	for i in mn:
		if d[i] != 1:
			p = False
			break
	if p:
		otv = 1
		for k in d:
			otv *= k
		print(otv, c + f)
		break
	for k in d:
		if d[k] % 2 == 1:
			d[k] += 1
			f = 1
			break
	c += 1
	for k in d:
		if d[k] % 2 == 1:
			f = 1
		d[k] = d[k] // 2 + d[k] % 2


import math
n = int(input())
multi_op = 0
sqrt_op = 0
multi = []
origin = n
while n >= 1:
	for i in range(1, n):
		ans = n * i
		sq = math.sqrt(ans)
		if int(sq) == sq:
			n = int(sq)
			sqrt_op += 1
			if i == 1:
				multi_op += 0
			else:
				multi_op += 1
			multi.append(i)
			break
	else:
		if multi_op > 0:
			op = sqrt_op + 1
		else:
			op = sqrt_op
		print(n, op)
		break


def primfacs(n):
	i = 2
	primfac = []
	arr = [0] * int(n)
	D = dict()
	while i * i <= n:
		while n % i == 0:
			if int(i) in D.keys():
				D[int(i)] += 1
			else:
				D[int(i)] = 1
			n = n / i
		i = i + 1
	if n > 1:
		if n in D.keys():
			D[n] += 1
		else:
			D[n] = 1
	return D

def main():
	n = int(input())
	go = 1
	op = 0
	res = 0
	D = primfacs(n)
	if n == 1:
		print('1', '0')
	else:
		while n ** (1 / 2) % 1 == 0:
			op += 1
			n = n ** (1 / 2)
		st = 0
		D = primfacs(n)
		for i in range(0, 25):
			ok = 1
			for el in D.keys():
				if not D[el] <= 2 ** i:
					ok = 0
			if ok == 1:
				st = i
				break
		op += st
		if st != 0:
			op += 1
		n = 1
		for el in D.keys():
			n *= el
		print(int(n), op)
main()