You are given an integer n find its next greater or equal number whose binary representation must not contain consecutive ones.

For eg. given n=6 whose binary is 110 and the next number with no consecutive ones is 8 whose binary is 1000.

INPUT

First line of input contains t, the total number of test cases. Then t line follows n.

0<t<100

0<n<10^5

OUTPUT

The next number on each line.