이진 쳐내기

두 사람이 "이진 쳐내기"라는 게임을 한다. 게임은 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 칸으로 이루어진 판에서 진행된다. 처음에 각 칸에는 말이 정확히 하나씩 놓여 있다. 두 사람은 번갈아 가며 수를 둔다.

한 번의 수는 다음과 같다. 번호가 $i$인 칸에 있는 말 하나를 골라 번호가 $2^k i$인 칸으로 옮긴다. 여기서 $k \ge 1$은 임의의 정수이며, 그 칸이 실제로 존재해야 한다. 즉 $2^k i \le n$이어야 한다. 옮겨 갈 칸에 이미 다른 말이 있었다면 두 말은 서로 쳐내어 모두 판에서 제거된다.

자기 차례에 어떤 수도 둘 수 없는 사람이 진다.

첫 번째 사람이 먼저 두고, 두 번째 사람이 나중에 둔다. 판의 크기 $n$을 잘 고르면 두 번째 사람에게 반드시 이기는 전략을 줄 수 있다. 예를 들어 크기가 $1$, $10$, $11$인 판이 그러하다. 두 번째 사람이 이기는 전략을 갖는 판의 크기를 작은 것부터 순서대로 나열했을 때, $k$번째 값을 구하여라.

입력의 유일한 줄에 정수 $k$가 주어진다 ($1 \le k \le 1\,000\,000\,000$).

두 번째 사람이 이기는 전략을 갖는 판의 크기를 작은 것부터 나열했을 때의 $k$번째 값을 한 줄에 출력한다.