Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P143PROH - ROUND 3H - Trò chơi

Tí và Tèo cùng chơi trò chơi đối kháng như sau:

1) Có n viên sỏi trong rổ, mỗi lượt, người chơi sẽ bốc 1 số viên sỏi trong rổ (ít nhất 1 viên và nhiều nhất là n viên). Tí là người đi trước, 2 người chơi luân phiên nhau.

2) Mỗi lượt, người chơi bốc ít nhất 1 viên, và nhiều nhất bằng 2 lần số viên sỏi mà người chơi trước vừa bốc. Lượt chơi đầu tiên Tí có thể bốc bao nhiêu tùy ý.

3) Người chơi nào lấy được viên sỏi cuối cùng sẽ là người chiến thắng.

Các bạn hãy xác định xem số viên sỏi nhỏ nhất Tí có thể bốc ở lượt đầu tiên để đảm bảo mình chắc chắn chiến thắng.

Input

Một số nguyên dương duy nhất n (n <= 10^15) là số viên sỏi có ban đầu.

Output

In ra số viên sỏi nhỏ nhất Tí bốc ở lượt đầu tiên để đảm bảo mình sẽ thắng cuộc.

Example

Test 1:

Input:

4

Output:

1

Giải thích test 1:

Lượt đầu tiên, Tí có thể bốc 1, 2, 3, 4 viên sỏi. Tí có thể lấy luôn cả 4 viên sỏi, và kết thúc cuộc chơi,
nhưng đây không phải là con số nhỏ nhất có thể.

Lượt 1, Tí bốc 1 viên, trong rổ còn 3 viên. Đến lượt Tèo, Tèo có thể bốc 1 viên hoặc 2 viên, nhưng đều
không thể chiến thắng được. Nếu Tèo bốc 1 viên, lượt sau Tí sẽ bốc 2 viên và giành chiến thắng,
nếu Tèo bốc 2 viên, lượt sau Tí bốc nốt 1 viên còn lại và giành chiến thắng.

 

Test 2:

Input:

7

Output:

2

 

Test 3:

Input:

8

Output:

8


Được gửi lên bởi:Admin
Ngày:2014-02-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.