1789: 一花依世界

> 一花一世界，一梦一千年。

可爱的小梦来到了八朝古都开封，这里有著名的小吃灌汤小笼包，小梦最喜欢吃小笼包了，正好这里有一家饭馆正在举行小笼包大赛，这个时候却碰到了食神bzj聚聚，虽然小梦很尊敬聚聚，但是对于吃饭这件事可是绝不心慈手软，bzj聚聚的实力也是不容小觑，大赛的规则如下：

有一大笼包子共n个，如果吃完了游戏就结束了。每一回合中双方可以进行以下两种动作之一：

1. 从笼中拿一个包子吃掉。
2. 从笼中拿一半包子吃掉，只有笼中包子为偶数时才可以进行这个动作。

现在小梦要和bzj聚聚进行比赛，且小梦先手，这一大笼包子根本不够小梦和bzj聚聚吃饱，双方都会尽可能多吃。小梦也是十分聪明的，双方都会按照最优策略吃小笼包。

第一行一个整数 t ，表示测试用例的个数。
接下来 t 行每行一个整数 n ，表示一笼有n个小笼包。
(1<=n<=10⁹)(1<=t<=10⁵)

2
5
6

2
4