Giảng viên của trung tâm luôn đưa ra cho lớp những bài toán thú vị để các em không bị nhàm chán.

Hôm nay vấn đề của giảng viên như sau:

Cho một số nguyên dương ~n~, bạn có thể thực hiện một trong các thao tác sau không hoặc nhiều lần:

• Nhân số ~n~ với số nguyên dương ~x~
• Lấy căn bậc ~3~ (cbrt) của ~n~ (nếu số ~n~ là lập phương của 1 số nguyên)

Bạn có thể thực hiện bao nhiêu thao tác cũng được.

Yêu cầu

Tìm giá trị bé nhất của ~n~ có thể đạt được và số lượng thao tác ít nhất để đạt được giá trị đó.

Input

Một dòng duy nhất là số nguyên dương ~n~ ~(n≤10^{18})~

Output

Một dòng duy nhất chứa 2 số nguyên, số đầu tiên là giá trị ~n~ bé nhất và số thứ hai là số lượng thao ít nhất tác cần thức hiện.

Sample Input 1

20

Sample Output 1

10 2

Subtask

• Có 50% số test ứng với 50% số điểm có ~n≤10^6~;
• Có 25% số test ứng với 25% số điểm có ~n≤10^{12}~;
• 25% số test còn lại tương ứng với 25% số điểm không có giới hạn gì thêm.