B. Stairs

B. Stairs

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Jett is tired after destroying the town and she wants to have a rest. She likes high places, that's why for having a rest she wants to get high and she decided to craft staircases.

A staircase is a squared figure that consists of square cells. Each staircase consists of an arbitrary number of stairs. If a staircase has nn stairs, then it is made of nn columns, the first column is 11 cell high, the second column is 22 cells high, ……, the nn-th column if nn cells high. The lowest cells of all stairs must be in the same row.

A staircase with nn stairs is called nice, if it may be covered by nn disjoint squares made of cells. All squares should fully consist of cells of a staircase.

This is how a nice covered staircase with 77 stairs looks like:

Find out the maximal number of different nice staircases, that can be built, using no more than xx cells, in total. No cell can be used more than once.

Input

The first line contains a single integer tt (1≤t≤1000)(1≤t≤1000)  — the number of test cases.

The description of each test case contains a single integer xx (1≤x≤1018)(1≤x≤1018)  — the number of cells for building staircases.

Output

For each test case output a single integer  — the number of different nice staircases, that can be built, using not more than xx cells, in total.

Example

input

Copy

4
1
8
6
1000000000000000000

output

Copy

1
2
1
30

Note

In the first test case, it is possible to build only one staircase, that consists of 11 stair. It's nice. That's why the answer is 11.

In the second test case, it is possible to build two different nice staircases: one consists of 11 stair, and another consists of 33 stairs. This will cost 77 cells. In this case, there is one cell left, but it is not possible to use it for building any nice staircases, that have not been built yet. That's why the answer is 22.

In the third test case, it is possible to build only one of two nice staircases: with 11 stair or with 33 stairs. In the first case, there will be 55 cells left, that may be used only to build a staircase with 22 stairs. This staircase is not nice, and Jett only builds nice staircases. That's why in this case the answer is 11. If Jett builds a staircase with 33 stairs, then there are no more cells left, so the answer is 11 again.

=========================================================================

首先能用n块颜色不重叠的正方形组成的阶梯，叫做好的阶梯

然后求x块积木能够最多组成多少不同的好的阶梯

1肯定是

2构造可知不是

3一定是

4不是

再由样例，只7也是

完全可以推出只用奇数列阶梯才能满足好的阶梯，那么剩下就是贪心了

#include<iostream>
# include<algorithm>
# include<unordered_map>

using namespace std;
typedef long long int  ll;

int main ()
{

    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll a=1;
        ll ans=0;
        while((a+1)*a/2<=n)
        {
            n-=(a+1)*a/2;
            a=a*2+1;
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;

}