完美洗牌

题目描述

​ 对于一副包含偶数张牌的纸牌，定义如下的“完美洗牌”：将一副牌等分为上下两叠，然后在两叠牌中逐张交错取牌：取上面一叠的第一张作为新的一叠的第一张，然后取下面一叠的第一张作为新的一叠的第二张，再取上面一叠的第二张作为新的一叠的第三张……如此交替直到所有的牌取完。例如，如果一副牌从上到下为“12345678”，在一次完美洗牌后变为“15263748”。如果要将一副 52 张的牌恢复为原来的顺序，需要的完美洗牌次数最少是8次.问：如果要将n 张的纸牌中的每一张的牌都恢复到最初的位置，需要的完美洗牌次数最少次数(至少一次)是多少。

输入格式

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

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

输出格式

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

输入输出样例

输入 #1

2
52
256

输出 #1

8
8

说明/提示

对于40%的数据,2<m<50。

对于60%的数据,Ai<=50。

对于100%的数据,2<m<1000000,𝑁<=10,Ai<30000。