• Cho số nguyên ~n~ phân tích ~n~ thành tích các thừa số nguyên tố.

Input

• Gồm duy nhất số nguyên dương ~n (2 \le n \le 10^{18})~.

Output

• Gồm nhiều dòng mỗi dòng gồm 2 số nguyên dương. Số đầu tiên là thừa số nguyên tố ~p~, số thứ hai là số mũ của ~p~ trong thừa số nguyên tố của ~n~.
• Chú ý: Cần sắp xếp các thừa số nguyên tố tăng dần theo thứ tự từ trên xuống.

Sample

Input #1

12

Output #1

2 2
3 1

Problem source: ducla0104