Quân vừa được bố mua cho một cái máy tính để chuẩn bị cho kỳ thi bấm máy sắp tới. Đề thi lần này là hàng loạt phép tính \(a + b\) với mọi \(0 \leq a, b \leq n\). Không cần suy nghĩ, Quân tự tin bấm máy và trở thành người nộp bài sớm nhất trước sự ngạc nhiên của mọi người.

Khi về đến nhà, Quân mới đọc hướng dẫn sử dụng và bàng hoàng khi phát hiện ra máy tính này tính XOR thay vì tổng như mong đợi. Hãy giúp Quân tính số phép tính mà anh ấy làm đúng nhé, nếu thấp quá thì Quân phải ra đường ngủ mất 😩

Input

• Chứa số nguyên \(n\) \((0 \leq n < 2 ^ {30})\).

Output

• Chứa một số nguyên là số phép tính mà Quân làm đúng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n < 2 ^ {10}\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3

9