Xenny has 2 positive integers A and B. He wants to find the prime factorization of the integer AB.
Input format:
Each line contains 2 space-separated integers A and B.
Output format:
Consider AB 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 <= 1012
1 <= B <= 1000