Giải bài trực tuyến

Pirate đi shopping ở Nhật Bản và sưu tập được rất nhiều đồng xu Nhật. Khi về nhà, anh đem các đồng xu ra chơi với em gái.

Trò chơi diễn ra như sau:

• Đầu tiên, Pirate chọn ra N đồng xu để chơi và chọn thêm một số nguyên K từ 0 đến N.
• Trong mỗi lượt chơi, Pirate hoặc em gái của mình sẽ đưa ra một cách chọn K đồng xu sao cho cách chọn đó không trùng với bất cứ cách chọn nào đã được sử dụng trước đó.
• Đến lượt của mình, ai không đưa ra được cách chọn nào nữa thì thua.

Pirate là một người anh mẫu mực nên anh luôn nhường em gái đi trước và luôn giành phần thua cho mình. Các bạn hãy tính xem có bao nhiêu cách chọn K để Pirate thua nhé.

Lưu ý: Một cách chọn K đồng xu là một bộ K số (a₁, a₂, ..., a_K) sao cho 1 ≤ a₁ < a₂ < ... < a_K ≤ N. Hai cách chọn (a₁, a₂, ..., a_K) và (b₁, b₂, ..., b_K) khác nhau nếu tồn tại a_i <> b_i (1 ≤ i ≤ K).

Input

• Một số nguyên N duy nhất.

Output

• Một số nguyên duy nhất thể hiện số cách chọn K để Pirate thua.

Giới hạn

• 1 ≤ N ≤ 10⁹
• 60% số test có 1 ≤ N ≤ 10³
• 80% số test có 1 ≤ N ≤ 10⁵

Example

Input:
4

Output:
2

Giải thích: Có 2 cách chọn K thỏa mãn là 0 và 4. Với K = 0, chỉ có một cách chọn các đồng xu (không chọn đồng xu nào cả) nên Pirate sẽ thua. Với K = 4 cũng tương tự.