Next Zog-Power Number

You are given an integer N. Your task is to find the smallest Zog-Power Number which is greater than or equal to N. A Zog-Power Number is defined as a power of 2 that contains the digit 1 at least once in its decimal representation. Mathematically, a power of 2 can be written as \(2^k\) for some non-negative integer \(k\), and the number is valid if its decimal representation contains the digit \(1\).

Example: If N = 9, the smallest power of 2 \(\ge 9\) is 16, and since 16 contains the digit 1, the answer is 16.

inputFormat

The input consists of a single integer N read from stdin.

outputFormat

Output a single integer to stdout: the smallest Zog-Power Number greater than or equal to N.

9

16