该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

完美洗牌

题目描述

​ 对于一副包含偶数张牌的纸牌，定义如下的“完美洗牌”：

将一副牌等分为上下两叠，然后在两叠牌中逐张交错取牌：

取下面一叠的第一张作为新的一叠的第一张，

然后取上面一叠的第一张作为新的一叠的第二张，

再取下面一叠的第二张作为新的一叠的第三张……

如此交替直到所有的牌取完。

例如，如果一副牌从上到下为“12345678”，在一次完美洗牌后变为“51627384”。

如果要将一副 52 张的牌恢复为原来的顺序，需要的完美洗牌次数最少是8次.

问：如果要将n 张的纸牌中的每一张的牌都恢复到最初的位置，需要的完美洗牌次数最少次数(至少一次)是多少。

输入格式

第一行共一个整数 $N$ ,表示询问次数。

以下 $N$ 行每行一个偶数 $m$ ,表示 $m$ 张的纸牌。

输出格式

一共 $𝑁$ 行，每行一个正整数 $A_i$ ,表示第 $i$ 次询问需要的完美洗牌最少次数。如果最少次数不存在,输出 $-1$ .

输入输出样例

输入 #1

2
65534
256

输出 #1

16
16

说明/提示

对于 $60$% 的数据, $A_i\leq60$。

对于 $100$% 的数据, $2<m<1e6,𝑁 \leq 10$。