Xenny has 2 positive integers A and B. He wants to find the prime factorization of the integer A^B.

Input format:

Each line contains 2 space-separated integers A and B.

Output format:

Consider A^B to have N prime factors.
Print N lines.
For every prime factor, print the base and the exponent separated by a single space.
The prime factors must be sorted by base.

Constraints:

1 ≤ A ≤ 10^12

1 ≤ B ≤ 1000

SAMPLE INPUT
10 1

SAMPLE OUTPUT
2 1
5 1
def factors(n):
	ans={}
	f=3
	while n % 2 == 0:
		if ans.has_key(2):
			ans[2]+=1
		else:
			ans[2]=1
		n /= 2
	while f * f <= n:
		while n % f == 0:
			if ans.has_key(f):
				ans[f]+=1
			else:
				ans[f]=1
			n /= f
		f += 2
	if n > 1:
		if ans.has_key(n):
			ans[n]+=1
		else:
			ans[n]=1
	return ans

a,b=map(int,raw_input().split())
ans=factors(a)
for i in sorted(ans.keys()):
	print i,(ans[i])*b