存在一个二进制字符串序列 $s_0, s_1, s_2, \dots$，其定义如下：

• $s_0 = 0$
• $s_i = s_{i-1} + b_i$

其中 $b_i$ 表示 $i$ 的二进制形式（不含前导零）。例如，$b_5 = 101$。$s_{i-1} + b_i$ 表示将字符串 $b_i$ 追加到 $s_{i-1}$ 的末尾。

序列的前几项如下： $s_0 = 0$ $s_1 = 01$ $s_2 = 0110$ $s_3 = 011011$ $s_4 = 011011100$ $s_5 = 011011100101$

令 $p_k$ 表示 $s_{10^{100}}$ 的长度为 $k$ 的前缀。给定 $k$，请计算 $p_k$ 中最长连续 $1$ 的长度。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。 对于每个测试用例，唯一的一行包含一个整数 $k$ ($1 \le k \le 10^9$)，表示前缀的长度。

输出格式

对于每个测试用例，输出一行一个整数，表示 $p_k$ 中最长连续 $1$ 的长度。

样例

输入格式 1

4
1
2
3
4

输出格式 1

0
1
2
2