A+B?!

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给你一个数x,你可以加一,减一,乘二,除二(向下取整),让你把x经过这些操作,操作成一个正整数y。使得y的十进制中非1的个数最少,如果有多解,输出操作步数最小的解。输出y。

Input

 先输入一个数n,然后有n行,每行一个正整数x(1<=x<=1024)。

Output

每行一个数y。

Sample Input

2
2
12

Sample Output

1
11

Hint

 

Source

第六届山东理工ACM网络编程擂台赛决赛