Next Sparse Number

Given an integer \(X\), find the smallest sparse number that is greater than or equal to \(X\). A number is called sparse if its binary representation does not contain two consecutive 1s. In other words, a number \(n\) is sparse if \(n \& (n >> 1) = 0\), where \(\&\) is the bitwise AND operator and \(>>\) is the right shift operator.

For example, consider \(X=6\). Its binary representation is 110 which has two consecutive 1s, hence it is not sparse. The smallest sparse number that is at least 6 is 8 (binary 1000).

inputFormat

The input consists of a single integer \(X\) provided via standard input (stdin).

outputFormat

Output the smallest sparse number greater than or equal to \(X\) to standard output (stdout).

6

8