Cho số nguyên dương ~n~, hãy phân tích ~n~ thành thừa số nguyên tố?

Ví dụ: 𝑛 = 36 → 𝑛 = 2 × 2 × 3 × 3. Khi đó có 2 thừa số 2 và 2 thừa số 3.

Dữ liệu

Một dòng duy nhất ghi số nguyên ~n~ ~(2\le n\le 10^{14})~.

Kết quả

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 đó.

Input 1

16

Output 1

2 4

Input 2

25

Output 2

5 2

Input 3

36

Output 3

2 2
3 2