Để chào đón Tết 2024, shop cô Ban có đặt mua nhiều bánh tét về để bán trong CLB. Độ dài của bánh là một số nguyên dương ~n~ và các khách hàng của cô cũng là những người sành điệu. Họ thích làm số học, đặc biệt là số square-free lớn hơn ~1~ nên yêu cầu cô Ban phải cắt bánh ra thành các đoạn nhỏ có độ dài square-free thì mới mua, không thì sẽ bom hàng. Chú ý: số squareg-free là nguyên dương không có ước chính phương nào khác ~1~, ví dụ: ~2,3,6,10,...~ là các số như vậy, còn ~4,12,16,18,...~ thì không.

Câu hỏi đặt ra là với một khúc bánh có độ dài ~n~ thì cô có thể bán cho nhiều nhất và ít nhất mấy người?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^{14}~ cho biết độ dài khúc bánh.

Output

Hai giá trị cho biết số người ít nhất và nhiều nhất mà cô có thể bán.

Sample input 1

1

Sample output 1

0 0

Sample input 2

8

Sample output 2

2 4

Giải thích: ở VD1, ta thấy độ dài khúc bánh là ~1~ thì không thể cắt nhỏ ra được nữa, còn với độ dài ~8~ thì có kiểu cắt thành: ~2+6~ hoặc ~2+2+2+2.~

Subtasks:

• Có 25% số test ứng với ~n \le 100.~
• Có 25% số test ứng với ~n \le 10^5.~
• Có 50% số test ứng với ~10^5 < n \le 10^{14}.~