바둑돌 게임

게임을 좋아하는 푸앙이는 요즘 "바둑돌 게임"이라는 게임을 즐겨 한다.

바둑돌 게임은 두 명이 번갈아 가며 한 개의 바둑돌 무더기에서 정해진 개수만큼 바둑돌을 가져가는 게임이다. 처음 시작한 사람은 바둑돌을 1개 가져가야 한다. 그다음 차례인 사람은 지난 차례에 가져간 개수보다 1개 많은 2개를 가져가야 한다. 그다음 차례에는 이전 차례보다 1개 많은 3개를 가져가야 한다. 이런 식으로 차례를 반복하다가 자신의 차례에 정해진 만큼의 바둑돌을 가져가지 못한 사람이 게임에서 진다.

게임의 규칙을 완벽하게 이해하고 있는 푸앙이는 같이 게임을 하기로 한 친구를 이기기 위해 바둑돌 무더기에 바둑돌을 추가하기로 했다. 바둑돌을 너무 많이 추가하면 친구가 수상하게 여길 수 있으므로, 추가하는 바둑돌은 가능한 한 적게 하려고 한다.

푸앙이가 먼저 게임을 시작한다고 할 때, 푸앙이가 게임에서 이기기 위해 추가해야 하는 바둑돌의 최소 개수를 구하는 프로그램을 작성하라. 단, 바둑돌을 추가하지 않아도 된다.

첫 번째 줄에 바둑돌 무더기에 있는 바둑돌의 개수를 나타내는 정수 $N$ $(1 \leq N \leq 100\,000)$이 입력된다.

푸앙이가 게임에서 이기기 위해 바둑돌 무더기에 추가해야 하는 바둑돌의 최소 개수를 출력한다.