HoangGiaMinh2k13 có một cỗ máy đặc biệt: Khi đưa 1 số \(N\) (\(N\) là số nguyên tố không chia hết cho \(2\) và \(3\)) vào máy, cậu ấy có thể bấm nút (x2) hoặc nút (x3) để nhân đôi hặc nhân ba số đó. Cậu ấy cho bạn của cậu ấy, là tk22LeAnhHao mượn nó. Sau một ngày tk22LeAnhHao đã trả lại HoangGiaMinh2k13 cái máy đó và một con số. Vốn quá tò mò, HoangGiaMinh2k13 muốn biết xem ngày hôm qua cậu bạn của mình đã lấy số gốc để nhân là bao nhiêu và đã bấm tổng cộng hai nút (x2) và (x3) bao nhiêu lần.

Input

• Chứa một số tự nhiên \(N\).

Output

• Số nguyên tố ban đầu và tổng số lần ấn nút.

Example

360

5
5