전북특별자치도 임실군은 우리나라 최초로 치즈 공장이 설립되어 치즈 생산을 처음 시작한 곳이며 치즈 만들기 등을 체험할 수 있는 임실치즈테마파크로도 유명하다.

테마파크에서 일하는 비버는 다음의 규칙에 따라 치즈를 생산한다.

우유를 남기지 않으면서, 정확히 n kg의 치즈를 생산하기 위해서 필요한 젖소는 최소 몇 마리인지 구해보자. 각 컨디션의 젖소의 수는 무한히 많다고 가정한다.

생산할 치즈의 무게(n)가 입력된다.

(1 <= n <= 10,000,000)

입력 예시 2

3

출력 예시 2

2