Bạn lại được ra 1 nhiệm vụ dễ dàng : Cho số nguyên ~n~ phân tích ~n~ thành 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 phân tích 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

Hint

Bài này cũng đơn giản thôi nhaa... Cố gắng AC nhá!!!!