2018 연세대학교 프로그래밍 경진대회

2015년, 2016년, 2017년에 이어 올해도 연세대학교 컴퓨터과학과 프로그래밍 경진대회가 열린다.

도현이는 교내 대회가 4년 연속 열린다는 사실에 감격해, 사비를 털 각오로 화려한 개막식을 준비했다.

도현이가 고른 것은 폭죽이다. 강의실 A528에서 천장을 다 뚫어버리며 터지는 화려한 폭죽이라면 모두가 좋아할 것이라고 생각했다. 도현이가 주문하려는 폭죽은 다음과 같이 터진다.

1. 처음 발사된 폭죽이 만든 대형 불꽃 하나는 적당한 높이에 도달하면 화려한 폭발과 함께 $K$개의 중형 불꽃으로 갈라진다.
2. 중형 불꽃 $K$개는 각각 다시 $K$개의 소형 불꽃으로 갈라지며 터진다.
3. 그 뒤 모든 불꽃은 소멸한다.

도현이는 적당한 폭죽을 찾아보려 했지만, 판매처에서는 $K$의 값을 알려주지 않았다. 대신 폭죽 하나가 만드는 전체 불꽃의 수만 알려줬다. 이 수는 처음 터진 대형 불꽃과 중형 불꽃, 소형 불꽃을 모두 포함한 값이다. 결국 도현이는 어떤 폭죽이 적당할지 알아내지 못해 폭죽을 사지 못했다.

도현이는 이 난제를 해결해주는 학생에게 이번 대회에서 맞힌 문제 수를 하나 늘려주기로 했다. 대회에서 우승하기 위해, 폭죽이 만드는 전체 불꽃의 수가 주어지면 $K$의 값을 찾아보자.

전체 불꽃의 수 $N$이 주어진다. ($3 \le N \le 10101$)

$K$의 값을 출력한다. 이 값은 정수임이 보장되며, 불가능한 경우는 입력으로 주어지지 않는다.