Lão Hạt, một tên trộm xảo quyệt từ xứ Dừa, trong một phi vụ trộm cắp tình cờ nhặt được chiếc đèn thần cổ. Tò mò, hắn xoa vào chiếc đèn, khiến thần đèn xuất hiện trong làn khói mờ ảo. Thần đèn hứa sẽ ban cho Lão Hạt ba điều ước, nhưng với điều kiện hắn phải chứng minh sự thông minh vượt trội.

Thần đèn đưa ra một bài toán:

*"Ta sẽ cho ngươi một số nguyên ~n~ và hãy phân thích thừa số của ~n!~" *

Là một kẻ ranh mãnh, Lão Hạt dẫu vậy cũng gặp đôi chút bối rối trước bài toán này. Dù nhanh trí, nhưng hắn chỉ quen xử lý những con số nhỏ hơn ~15!~. Thế là, không còn cách nào khác, hắn tìm đến sự giúp đỡ của bạn thân - chính là bạn.

* Input *

• Dòng đầu tiên và duy nhất là một số nguyên ~n~ ~(1 \le n \le 5 \times 10^5)~.

* Output*

• In ra thừa số nguyên tố của số đó theo thứ tự tăng dần và số mũ cách nhau bởi một khoảng trắng trên mỗi dòng.

Sample Input 1

4

Sample Output 1

2 3
3 1

Sample Input 2

2

Sample Output2

2 1

Note

• Đây là Lão Hạt chứ không phải Lão Hạc.