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

见题面

见题面