Problem: 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

Solution (in PYTHON):

Solution:
import math
primelist=[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]
skiplist=[1,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,179,191,193,197,199]

def isprime(p):
#    print p
    i=0
    temp=math.sqrt(p)
#    print temp
    while(primelist[i]<temp):
#        print primelist[i]
        if(p%primelist[i]==0):
            break
        else:
            i=i+1
    if(primelist[i]>temp):
#        primelist.append(p)
        return 1
    else:
        return 0
a,b=map(int,raw_input().split())
sqrt_a=math.sqrt(a)
list_limit=int(sqrt_a/200)
if a==1:
    print a,a
for i in xrange(1,list_limit):
    for j in range(0,43):
        temp=210*i+skiplist[j]
        if(isprime(temp)):
            primelist.append(temp)
#            print temp
#print primelist[-1]
for z in primelist:
    count=0
    while(a%z==0):
 #       print "The a is:",a,"The z is:",z
        a=a/z
        count+=1
#        print "now a is:",a
    if(count>0):
        print z,count*b
    if a<=1:
 #       print "before breaking",a
        break
else:
    print a,b