Viết chương trình nhập vào một số nguyên dương \(n\) (\(1 \le n \le 10^6\)). Phân tích \(n\) thành các thừa số nguyên tố và in kết quả theo thứ tự tăng dần.

Input

Một dòng chứa số nguyên dương \(n\).

Output

In ra các thừa số nguyên tố của \(n\) theo thứ tự tăng dần, mỗi số cách nhau bởi một dấu cách. Nếu \(n = 1\), in ra 1.

Ví dụ