Cho số nguyên \(n\). Hãy phân tích \(n\) thành tích các thừa số nguyên tố.

Ví dụ: \(n=36 \rightarrow n=2\times2\times3\times3\). Khi đó có \(2\) thừa số \(2\) và \(2\) thừa số \(3\).

Input

• Vào từ thiết bị nhập chuẩn gồm dòng duy nhất chứa một số nguyên dương \(n\) \((n\le{10}^{14})\).

Output

• Ghi ra thiết bị xuất chuẩn gồm các ước nguyên tố xếp từ nhỏ đến lớn của \(n\) cùng số lần xuất hiện trong cách phân tích đó.

Example

16

2 4

25

5 2

36

2 2
3 2