考虑一场季后赛,其中 $$$2^n$$$ 运动员参加比赛。运动员编号从 $$$1$$$ 到 $$$2^n$$$。
锦标赛分 $$$n$$$ 个阶段举行。在每个阶段,运动员都会被分成两组,每个运动员都属于一对。在每一对中,运动员相互竞争,最后只有一个人获胜。每对的获胜者晋级下一阶段,失败的运动员被淘汰出局。
这些对的形成如下:
- 第一阶段,运动员$$$1$$$与运动员$$$2$$$竞争; $$$3$$$ 与 $$$4$$$ 竞争; $$$5$$$ 与 $$$6$$$ 竞争,依此类推;
- 第二阶段,“$$$1$$$–$$$2$$$”比赛的获胜者与“$$$3$$$–$$$4$$$”比赛的获胜者进行比赛;比赛“$$$5$$$–$$$6$$$”的获胜者与比赛“$$$7$$$–$$$8$$$”的获胜者竞争,依此类推;
- 接下来的阶段按照相同的规则进行。
当运动员$$$x$$$和$$$y$$$比赛时,获胜者的决定如下:
- 如果 $$$x+y$$$ 为奇数,则指数较低的运动员获胜(即如果 $$$x < y$$$,则 $$$x$$$ 获胜,否则 $$$y$$$ 获胜);
- 如果 $$$x+y$$$ 为偶数,则指数较高的运动员获胜。
下图描述了 $$$n = 3$$$ 的锦标赛的进行方式。
你的任务如下:给定整数 $$$n$$$,确定赢得比赛的运动员的索引。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 30$$$) — 测试用例的数量。
每个测试用例由一行组成,其中包含一个整数 $$$n$$$ ($$$1 \le n \le 30$$$)。
输出
对于每个测试用例,打印一个整数 - 锦标赛获胜者的索引。
示例
输入 #1
2 3 1
输出 #1
7 1
注意
语句中的图片显示了 $$$n = 3$$$ 的情况。
如果 $$$n = 1$$$,则运动员 $$$1$$$ 和 $$$2$$$ 之间只有一场比赛。由于 $$$1 + 2 = 3$$$ 是奇数,因此指数较低的运动员获胜。因此,运动员 $$$1$$$ 是获胜者。