Aditi and Magic Trick

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
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
 Subtask #1: 1 ≤ T ≤ 10, 1 ≤ N ≤ 10 (5 points)
 Subtask #2: 1 ≤ T ≤ 100, 1 ≤ N ≤ 1000 (10 points)
 Subtask #3: Original Constraints (85 points)
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.
Author:  abhra73 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/ADMAG 
Tags  abhra73, aug15, fibonacci, simple, zeckendorf 
Date Added:  29062015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions