The binary weight of a number is the amount of 1s in the number's binary representation. For example, 43 in binary is 101011, so the binary weight is 4. Given a decimal number, we want to find the next greater decimal number that has the same binary weight. In this case, 45 (101101) is such a number.

The input file DATA3.txt will contain 5 lines, integers 1 <= N <= 1_000_000_000

The output file OUT3.txt will contain 5 lines, each corresponding to the next decimal number with the same binary weight as in the input.

Reminder: a binary representation of a number is the sum of powers of 2, where 1 means that power is included, and 0 means that it's not. So a binary 43 is 1*2⁵ + 0*2⁴ + 1*2³ + 0*2² + 1*2¹ + 1*2⁰, which evaluates to 1*32 + 0*16 + 1*8 + 0*4 + 1*2 + 1*2 = 32 + 8 + 2 + 1 = 43 (101011).

3
4
10
7
8
		        

5
8
12
11
16