Đề bài

Cho một số nguyên dương $N$. Hãy phân tích $N$ thành tích của các thừa số nguyên tố. Kết quả in ra theo dạng thừa_số^số_mũ.

Dữ liệu vào

•Một số nguyên dương $N$ ($2 \le N \le 10^9$).

Dữ liệu ra

Các cặp thừa_số và số_mũ in trên các dòng khác nhau hoặc cách nhau bởi dấu cách.

Ví dụ