Phân tích số nguyên dương \(N\) thành tích các thừa số nguyên tố: \(N = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}\).

Định dạng đầu vào

• Một dòng duy nhất chứa số nguyên dương \(N\) (\(2 \le N \le 10^{12}\)).

Định dạng đầu ra

• In ra các thừa số nguyên tố và số mũ tương ứng theo định dạng p e tăng dần theo \(p\).

Ví dụ

Input:

60

Output:

2 2
3 1
5 1

Giải thích: \(60 = 2^2 \times 3^1 \times 5^1\).

Ràng buộc & Subtasks