tyEyyu53的游戏

题目描述

这天，tyEyyu53学长正在家中午睡，突然一道强光让他失去了意识。当他醒来后，发现自己在外星人的飞船上，飞船正在飞往外星人的母星。

被抓来的人算上tyEyyu53学长共有 $n$ 人，外星人要和他们玩一个游戏：

这 $n$ 人需要排成一个队伍，外星人让第一个人开始从 $1$ 报数，报数结束后数字为奇数的人会被外星人带走。接着进入第二轮，第一个人开始从 $1$ 报数，奇数的人会被带走，以此类推进行了若干轮，如果队伍中只剩下一个人时，外星人会放这个人回去。

因为tyEyyu53学长担心自己不习惯外星上的饮食，于是觉得还是地球比较好，请你帮帮他告诉他应该站在队伍中的哪个位置。

输入格式

每个测试点有多组数据，第一行 $t(1\leq t \leq 100)$ 表示有多少组数据，接下来第 $2$ 到 $t + 1$行，每行给出一个整数 $n（1 \leq n \leq 10^{15}）$ ，表示被抓到飞船上的人的数量。

输出格式

对于每组数据，需要输出一行为tyEyyu53学长需要站在的位置。

样例 #1

样例输入 #1

2
6
8

样例输出 #1

4
8

提示

第一行 $2$ 表示样例共有两组数据。

对于第一组数据，共有 $6$ 人，我们用 $A,B,C,D,E,F,G$ 表示不同的人，第一轮报数为： $1,2,3,4,5,6$ ,其中 $A,C,E,G$ 会被带走。到第二轮，剩下的人是 $B,D,F$ 重新报数为：$1,2,3$ ，其中 $B,F$ 会被带走，最后只剩下 $D$，所以学长只需要站在 $D$ 的位置，即 $4$。

对于第二组数据，共有 $8$ 人，我们用 $A,B,C,D,E,F,G,H,I$ 表示不同的人，第一轮报数为： $1,2,3,4,5,6,7,8$ ,其中 $A,C,E,G,I$ 会被带走。到第二轮，剩下的人是 $B,D,F,H$ 重新报数为：$1,2,3,4$ ，其中 $B, F$ 会被带走。进入第三轮，剩下 $D,H$，重新报数为：$1,2$ ，其中 $D$ 会被带走，最后只剩下 $H$所以学长只需要站在 $H$ 的位置，即 $8$。