야노시크

로빈 후드라고도 불리는 야노시크는 부자의 재물을 빼앗아 가난한 사람에게 나눠 준다. 야노시크와 그의 패거리는 백작의 성으로 금을 나르던 수송대를 습격해 궤짝 $n$개를 빼앗았다. 전리품을 동굴로 옮겨 놓고 세어 보니 $i$번 궤짝($i = 1, 2, \dots, n$)에는 금이 가득 든 자루가 정확히 $i$개 들어 있었다.

가난한 사람이 금화를 몇 닢 얻으러 오면 야노시크는 다음 절차를 따른다. 먼저 비어 있지 않은 궤짝 중에서 자루가 가장 적게 든 궤짝 하나를 고른다.

• 고른 궤짝에 자루가 정확히 하나 있으면 그 자루를 찾아온 사람에게 건네주고, 그 사람은 기뻐하며 돌아간다.
• 자루가 둘 이상이고 그 개수가 홀수이면 자루 하나를 자기 주머니에 넣고 절차를 처음부터 다시 시작한다.
• 자루 개수가 짝수이면 정확히 절반을 꺼내 빈 궤짝에 옮겨 담고(동굴에 빈 궤짝은 넉넉하다) 절차를 처음부터 다시 시작한다.

비어 있지 않은 궤짝이 하나라도 남아 있으면 절차를 여러 번 반복하더라도 찾아온 사람은 금 자루 하나를 반드시 받아 간다. 가난한 사람은 궤짝이 모두 빌 때까지 야노시크의 동굴을 찾아온다.

패거리는 두목이 도적의 이름을 더럽히는 것은 아닌지 신경 쓴다. 궤짝이 모두 비었을 때 야노시크의 주머니에 남은 금 자루가 몇 개인지 구하라.

첫째 줄에 야노시크 패거리가 빼앗은 궤짝의 개수 $n$($1 \le n \le 10^9$)이 주어진다.

궤짝이 모두 빈 뒤 야노시크의 주머니에 남은 금 자루의 개수를 한 줄에 출력한다.