K. Longest Continuous 1
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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}$$$.

$$$s_0$$$$$$s_1$$$$$$s_2$$$$$$s_3$$$$$$s_4$$$$$$s_5$$$$$$\dots$$$
$$$\texttt{0}$$$$$$\texttt{01}$$$$$$\texttt{0110}$$$$$$\texttt{011011}$$$$$$\texttt{011011100}$$$$$$\texttt{011011100101}$$$$$$\dots$$$

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$$$.

Input

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.

Output

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

Example
Input
4
1
2
3
4
Output
0
1
2
2