A13852 | Stairs

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.

Staircase is a squared figure that consists of square cells. Each staircase consists of an arbitrary number of stairs. If a staircase has $n$ stairs, then it is made of $n$ columns, the first column is $1$ cell high, the second column is $2$ cells high, $\ldots$ , the $n$ -th column if $n$ cells high. The lowest cells of all stairs must be in the same row.

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

This is how a nice covered staircase with $7$ stairs looks like: Find out the maximal number of different nice staircases, that can be built, using no more than $x$ cells, in total. No cell can be used more than once.

The first line contains a single integer $t$ $(1 \le t \le 1000)$ — the number of test cases.

The description of each test case contains a single integer $x$ $(1 \le x \le 10^{18})$ — the number of cells for building staircases.

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