409385: GYM103495 K Longest Continuous 1

There is a sequence of binary strings $$$s_0,s_1,s_2,\dots$$$, which can be defined by the following recurrence relation:

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

Here $$$b_i$$$ means the binary form of $$$i$$$ without leading zeros. For example, $$$b_5=\texttt{101}$$$. And $$$s_{i-1}+b_i$$$ means to append string $$$b_i$$$ to the back of $$$s_{i-1}$$$.

Let's use $$$p_k$$$ to denote the prefix of $$$s_{10^{100}}$$$ of length $$$k$$$. Now given $$$k$$$, please calculate the length of the longest continuous $$$\texttt{1}$$$ in $$$p_k$$$.

The first line of the input contains one integer $$$T$$$ ($$$1\le T\le 10^4$$$), indicating the number of test cases.

For each test case, the only line contains one integer $$$k$$$ ($$$1\le k\le 10^9$$$), indicating the length of the prefix.

For each test case, output one integer in a single line, indicating the length of the longest continuous $$$\texttt{1}$$$ in $$$p_k$$$.

4
1
2
3
4

0
1
2
2