暂无测试数据。

小 $D$ 喜欢合并果子，但他最初没有果子。

他可以花费 $1$ 滴汗水从商店中买来 $1$ 个果子（可以购买多次），可以将一堆果子的数量翻倍，不需要花费汗水，也可以将两堆大小只相差 $1$ 的果子轻松合并，不需要花费汗水。

小 $D$ 必须将合并好的所有果子带回家，但小 $D$ 不喜欢出多余的汗水。

比如说一堆果子只需要 $2$ 滴汗水就可以得到，那么小 $D$ 绝不会花 $>2$ 滴汗水来得到。

但小 $D$ 喜欢出汗，所以她想知道最后带回家的果子个数在 $[1,2n+1]$ 时，可以出的最多汗水是多少。

但是他不会算，而且小 $D$ 也不喜欢一堆偶数个的果子，所以最后带回家的果子个数不能是偶数。作为小 $D$ 的好朋友，你能告诉他，他可以出的最多汗水是多少吗？

形式化的，令 $f(i)$ 表示最后带回家 $i$ 个果子时，需要出的最少汗水，求 $\max\{f(i)|i\in[1,2n+1] \& i\bmod 2=1\}$。

输入格式

第一行一个整数 $T$ 表示数据组数。

下面 $T$ 行每行一个 $n$，表示一次询问。

输出格式

输出 $T$ 行，每行一个整数表示答案。

数据范围

对于 $50\%$ 的数据，有 $T=1,n\leq 10^7$。

对于 $80\%$ 的数据，有 $T=1,n\leq 10^{100}$。

对于 $100\%$ 的数据，有 $1\leq T\leq 10^4,1\leq n\leq 10^{100}$。

2
5
10

5
8