상덕이와 희원이는 동전 게임을 하면서 시간을 보낸다. 동전 게임은 동전 N개를 가지고 하는 게임이고, 규칙은 다음과 같다.

1. 상덕이가 먼저 게임을 하고, 그 다음엔 희원이, 그 다음에 상덕이, 희원이 순서대로 게임을 한다. 순서대로 첫 번째 턴, 두 번째 턴, 세 번째 턴, ...
2. 상덕이는 첫 번째 턴에서 가져갈 수 있는 동전의 개수는 1보다 크거나 같고, N보다 작거나 같다.
3. 그 다음 턴부터는 동전을 이전 턴에서 그 사람이 가져간 동전 개수의 최대 2배만큼 가져갈 수 있다. (동전을 적어도 1개는 가져가야 한다)
4. 이렇게 플레이를 하다가 마지막 동전을 가져가는 사람이 이긴다.

상덕이와 희원이가 항상 최적의 방법으로 게임을 한다. 이 말은 어떤 상황에서 플레이어 A가 B를 항상 이길 수 있다면, A가 항상 이긴다는 것이다.)

이때, 상덕이가 이기기 위해서는 첫 번째 턴에서 동전을 몇 개 가져가야 하는지를 구하는 프로그램을 작성하면 된다. 이러한 동전의 개수가 여러 개 나올 수 있는데, 그 때는 가장 적은 개수를 출력하면 된다.

입력 형식

첫째 줄에 동전의 개수 N이 주어진다. (2 ≤ N ≤ 10¹⁵)

출력 형식

첫째 줄에 상덕이가 이기기 위해서 가져가야 하는 동전 개수의 최솟값을 출력한다.

예제 입력 1

4

예제 출력 1

1

예제 입력 2

7

예제 출력 2

2

예제 입력 3

8

예제 출력 3

8

힌트

동전의 개수가 4개일 때, 상덕이가 첫 번째 턴에서 가져갈 수 있는 동전의 경우의 수는 1, 2, 3, 4개이다. 만약 4개를 가져가게 된다면 상덕이는 항상 이기게 된다. 하지만, 이것은 최솟값이 아니다. 상덕이가 첫 번째 턴에서 동전을 1개 가져갔다고 생각해보자. 그럼 이제 동전은 3개가 남고, 희원이는 동전을 많아야 2개만 가져갈 수 있기 때문에 절대 이길 수 없게 된다. (문제의 3번 조건 때문에 희원이는 동전을 1*2개까지 가져갈 수 있다) 희원이가 동전을 1개를 가져가던, 2개를 가져가던 상덕이는 다음 턴에서 남은 동전을 모두 가져갈 수 있기 때문에 상덕이가 첫 번째 턴에서 동전을 1개 가져가면 항상 이기게 된다. 따라서 정답은 1이다.