33677번 - 푸앙이와 콩나무

문제

잭과 콩나무를 감명 깊게 읽은 푸앙이는 동화책에 나오는 신비한 힘을 지닌 콩을 구해 하늘나라에 있는 거인의 성에 올라가려고 한다. 하지만 신비한 힘을 지닌 콩을 구하지 못한 푸앙이는 대신 평범한 콩나무에 하루에 한 번씩 물을 주어 하늘나라에 올라가려 한다. 콩나무는 다음 규칙을 따라 자란다.

• 물을 1ドル$만큼 주면 다음 날 콩나무의 길이가 1ドル$ 증가한다.
• 물을 3ドル$만큼 주면 다음 날 콩나무의 길이는 3ドル$배가 된다.
• 물을 5ドル$만큼 주면 다음 날 콩나무의 길이는 제곱이 된다.
• 다른 양의 물을 준 경우에는 콩나무의 길이가 변하지 않는다.

0ドル$번째 날의 초기 콩나무 길이는 0ドル$이다. 푸앙이가 거인의 성에 도착하려면 콩나무의 길이가 정확히 $N$이 되어야 하며, 콩나무의 길이가 $N$이 된 날에 푸앙이는 거인의 성에 도착할 수 있게 된다. 푸앙이가 거인의 성에 도착하려면 적어도 며칠이 필요할지와 적어도 얼마나 물이 필요할 지 구해보자.

입력

첫 번째 줄에 거인의 성에 도착하기 위해 필요한 콩나무의 길이 $N$이 주어진다.

출력

첫 번째 줄에 푸앙이가 거인의 성에 도착하기 위해 필요한 최소 일수와 최소 일수만에 거인의 성에 도착하기 위해 필요한 물의 양의 최솟값을 공백으로 구분하여 출력한다.

제한

• 0ドル \le N \le 1,000円,000円$

노트