Practice Greedy algorithms and Mathematics with the exercise "Non-Triple Numbers"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Greedy algorithms
Mathematics

Statement

Goal

You must find the smallest non-triple number greater than a given integer. A triple number is one whose binary representation contains three or more consecutive 1s or 0s.

Input

Line 1: A single decimal integer n

Output

Line 1: The smallest decimal integer greater than n that does't contain three consecutive 1s or 0s when converted to binary

Constraints

1 ≤ n ≤ 10^10

Example

Input

Output

Solve it

A higher resolution is required to access the IDE