시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 165 44 38 33.043%

문제

최근 키파는 빵 만드는 방법을 배웠다. 키파는 빵밖에 만들 줄 모르지만 케이크를 만들고 싶어서 윗면이 정사각형 모양인 직육면체 모양의 빵에 생크림을 얇게 발랐다. 물론 모든 면에 다 바른 건 아니고, 윗면과 옆면 총 다섯 면에만 발랐다. 키파는 처음 만든 케이크(?)를 N명의 친구에게 선물했다. N명의 친구는 아주 계산적이어서 다른 사람과 자기가 먹는 빵의 양뿐만 아니라 생크림의 양까지 같다는 것이 보장되어야 만족하고 자신의 케이크(?) 조각을 먹는다. 키파가 케이크(?)를 어떻게 잘라야 가장 적은 횟수로 자르면서 만족하고 케이크(?) 조각을 먹게 할 수 있을까? 자를 때는 윗면에 수직인 면으로 끝에서 끝까지 완전히 잘라야 하며, 중간에 칼질을 멈추거나, 자른 조각을 이동하면 안 된다. N조각보다 더 많이 잘라서 여러 조각을 한 사람에게 나누어 주는 것은 상관없다. 키파는 빵을 일정한 크기로 굽는 법을 모르기 때문에 케이크(?)의 크기는 알 수 없다. 다만 같은 길이의 자를 써서 케이크(?)의 가로와 세로 크기를 맞추기 때문에 그 둘만큼은 똑같다고 가정해도 된다.

입력

첫째 줄에 1018 이하의 자연수 N이 주어진다. 그게 다다!

출력

자르는 방법은 알고 있으니까 자르는 것이 언제 끝날지 궁금해하는 사람을 위해 첫째 줄에 자르는 최소 횟수만을 출력하라.

예제 입력

8

예제 출력

4

힌트

출처

  • 문제를 만든 사람: kipa00