Aditi recently discovered a new magic trick. First, she gives you an integer N and asks you to think an integer between 1 and N. Then she gives you a bundle of cards each having a sorted list (in ascending order) of some distinct integers written on it. The integers in all the lists are between 1 and N. Note that the same integer may appear in more than one card. Now, she shows you these cards one by one and asks whether the number you thought is written on the card or not. After that, she immediately tells you the integer you had thought of.
Seeing you thoroughly puzzled, she explains that she can apply the trick so fast because she is just adding the first integer written on the cards that contain the integer you had thought of, and then gives the sum as the answer. She calls a bundle interesting if when the bundle is lexicographically sorted, no two consecutive cards have any number in common. Now she challenges you to find out the minimum number of cards she will need for making an interesting bundle such that the magic trick will work every time.

Input

The first line of the input contains an integer T denoting the number of test cases.
Each test case contains a line with a single integer N.

Output

For each test case, output a line containing a single integer denoting the minimum number of cards required.

Constraints

1 ≤ T ≤ 10^5
1 ≤ N ≤ 10^18

Sub tasks

Example
Input:
2
1
4

Output:
1
3

Explanation

In example 1, only 1 card containing {1} will work.
In example 2, make 3 cards containing {1,4}, {2} and {3,4}.

Assume you thought of 1, then you will select the 1^st card {1,4}, then she will correctly figure out the integer you thought being 1.
Assume you thought of 2, then you will select the 2^nd card {2}, then she will correctly figure out the integer you thought being 2.
Assume you thought of 3, then you will select the 3^rd card {3,4}, then she will correctly figure out the integer you thought being 3.
Assume you thought of 4, then you will select 1^st card {1,4} and 3^rd card {3,4}, then she will calculate the sum of the first integers of the two card 1 + 3 = 4, and she will answer it.

Thus her trick will work well in every case. And we can check it easily that the cards are sorted in lexicographical order and two consecutive cards have no common integers.

见题面

见题面