ADMAG.md

category_name	problem_code	problem_name	languages_supported	max_timelimit	source_sizelimit	problem_author	problem_tester	date_added	tags	editorial_url	time	layout
easy	ADMAG	Aditi and Magic Trick	ADA ASM BASH BF C C99 strict CAML CLOJ CLPS CPP 4.3.2 CPP 4.9.2 CPP14 CS2 D ERL FORT FS GO HASK ICK ICON JAVA JS LISP clisp LISP sbcl LUA NEM NICE NODEJS PAS fpc PAS gpc PERL PERL6 PHP PIKE PRLG PYPY PYTH PYTH 3.4 RUBY SCALA SCM chicken SCM guile SCM qobi ST TCL TEXT WSPC	1	50000	abhra73	laycurse	29-06-2015	abhra73 aug15 fibonacci simple zeckendorf	http://discuss.codechef.com/problems/ADMAG	view_start_date submit_start_date visible_start_date end_date current 1439803800 1439803800 1439803800 1735669800 1493558104	problem

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 ≤ 105
• 1 ≤ N ≤ 1018

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 1st 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 2nd card {2}, then she will correctly figure out the integer you thought being 2.
  • Assume you thought of 3, then you will select the 3rd card {3,4}, then she will correctly figure out the integer you thought being 3.
  • Assume you thought of 4, then you will select 1st card {1,4} and 3rd 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.