Giang hồ đồn đại rằng

Ngành IT Việt Nam hiện nay ở đầu của sự phát triển. Có thể nói IT là vua của các nghề. Vừa có tiền, có quyền. Vừa kiếm được nhiều $ lại được xã hội trọng vọng.

Vì thế Liên Hợp Quốc - United Nations hay còn gọi là UN đã mời các chuyên gia để tổ chức kì thi UN Hacker Jam với quy mô sánh với các kì thi lập trình thường niên nổi tiếng như Google Code Jam và Facebook Hackercup. Bạn Bảo Anh - một coder kì cựu đã tham gia cuộc thi và xuất sắc đánh bại nhiều đối thủ mạnh trên thế giới như tourist, tourguide, ... và lọt vào vòng cuối cùng. Tuy nhiên anh ấy mãi vẫn không thể chiến thắng trước bàn tay trái.. - à không, là phân thân của chính mình. Chả là trước khi thi anh ta đã phân thân chi thuật để giảm công lực xuống 1 nửa, với mục đích giao lưu học hỏi là chủ yếu, ai ngờ thắng luôn nên đành phải thi đấu với cái bóng của bản thân. Hội đồng UN thấy vậy chỉ biết thở dài ngao ngán, đành tổ chức một trò chơi trí tuệ để Bảo Anh tự xử. Trò chơi như sau :

Đầu tiên, UN sẽ đưa ra số \(N > 1\). Bảo Anh và cái bóng của anh ấy sẽ thay phiên nhau chơi từng lượt. Tại lượt của một người chơi, người đó phải chia \(N\) cho lũy thừa \(p^k (k \ge 1)\) với \(p\) nguyên tố và \(p^k\) là ước của \(N\). Người đưa số \(N\) về giá trị \(1\) là người chiến thắng. Bảo Anh biết rằng đối thủ cũng đi toàn nước tối ưu như mình vậy, vì thế với \(N\) bất kì anh ấy luôn biết được người thắng là người đi trước hay người đi sau. Nói cách khác - trò chơi đã kết thúc trước cả khi nó bắt đầu. UN cũng biết trò này quá đơn giản nên đã tăng độ khó, đặt câu hỏi như sau : Trò chơi sẽ kết thúc sau bao nhiêu lượt? Người chơi biết mình thua sẽ cố gắng câu giờ hết sức có thể, ngược lại người sẽ thắng muốn trò chơi kết thúc càng sớm càng tốt. Bảo Anh nghĩ ngợi một lúc và đã có đáp án nhưng không tự tin lắm vì cái bóng của anh ta đang giở một nụ cười hết sức nham hiểm (chỉ có bản chính mới phải suy nghĩ câu trả lời đúng thôi chứ bản sao chỉ việc gây hoang mang tinh thần là xong). "Chắc chưa?" - một câu hỏi đơn giản đã làm coder kì cựu nhất phải toát mồ hôi hột. Vì thế xin nhờ các bạn thí sinh mách nước cho Bảo Anh bằng cách đưa ra đáp án đúng nhé 😉.

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(N > 1\)

Output

• Gồm một dòng duy nhất chứa đáp án của bài toán

Scoring

• Subtask #1 (\(5\%\) số điểm): \(N = p^3, N \le 10^{18}, p\) là SNT.
• Subtask #2 (\(15\%\) số điểm): \(N = 6^x\) với \(1 \le x \le 20\)
• Subtask #3 (\(35\%\) số điểm): \(N \le 1052004\)
• Subtask #4 (\(50\%\) số điểm): \(N \le 1234567987654321\)

Example

18

3