时间限制：1000ms

空间限制：512MB

问题描述

梦梦苦学扑克技术，终于成为了卡牌大师。

卡牌大师的基本功之一就是切牌。

现在梦梦有一副 $2n$ 张的扑克牌，其中第 $i$ 张卡牌上写着数字 $i$，一开始卡牌的顺序是按照 $1,2,\cdots,2n$ 的顺序给出的。

为了练习切牌操作，梦梦进行了操作，将卡牌均分分成两堆后穿插合并，将 $a_1,a_2,\cdots,a_{2n}$ 变成 $a_1,a_{n+1},a_2,a_{n+2},\cdots,a_{n},a_{2n}$。

梦梦想知道至少要进行多少次切牌操作，才能将卡牌的顺序重新变为 $1,2,…,2n$。

输入格式

输入第一行，包含 $1$ 个正整数 $T$，表述数据组数。

对于每组数据，第一行给定正整数 $n$。

输出格式

对于每组数据，输出一行，表示答案。

样例输入

5
3
5
114514
1919810
1145141919810

样例输出

4
6
229026
182838
1145137056372

样例解释

对于第一组数据，第一次操作后，序列变为 $1,4,2,5,3,6$。

第二次操作后，序列变为 $1,5,4,3,2,6$。

第三次操作后，序列变为 $1,3,5,2,4,6$。

第四次操作后，序列变为 $1,2,3,4,5,6$。

评测数据规模

对于 $30\%$ 的数据，$1 \leq n \leq 10^3$。

对于 $60\%$ 的数据，$1 \leq n \leq 10^7$。

对于所有测评数据，$1 \leq T \leq 5,1 \leq n \leq 10^{14}$。