Biswa and Borhani
Biswa has started Borhani (kind of a soft drink) business recently and made it the new sexy in no time. He is dealing in very big numbers now and going to open branches all over the world. For each branch, he knows the maximum amount of Borhani any customer can order. As Borhani is liquid, customers order Borhani in litres and more specifically they order in positive integer quantity. For a particular branch, any quantity between 1 and the maximum limit of that branch can be ordered. Cups of different sizes are used to measure Borhani. Each cup can measure a positive quantity and Biswa has got stock of unlimited cups of each positive capacity. Now he want to send minimum number of cups to each of the branches so that all the positive quantity between 1 and the maximum limit of that branch can be measured. While measuring a particular quantity, any of the available cups in that branch can be used at most once.
Input
First line of the test case contains a positive integer T (≤ 105) denoting the number of branches. Then in the following T lines there will be a positive integer N (1 ≤ N ≤ 1018) in each one denoting the maximum limit of that branch.
- Dataset - Small (10 points): N ≤ 16
- Dataset - Medium (20 points): N ≤ 100
- Dataset - Large (30 points): N ≤ 105
- Dataset - Extra Large (40 points): Original Constraints
Output
For each of the branches, the minimum number of cups required should be given as output.
Sample
| Input | Output |
|---|---|
3 2 3 5 | 2 2 3 |
Explanation
- For the first branch, maximum limit is 2. Cups of capacity 1 and 2 can be sent there to measure 1 and 2 litres of Borhani. So the answer is 2.
- For the second branch, maximum limit is 3. Cups of capacity 1 and 3 can be used.
- For measuring 1 litre, just fill up the cup with 1 litre capacity.
- For measuring 2 litres, fill up the cup with capacity 3 and then fill up the cup with capacity 1 using the Borhani from cup with capacity 3. Finally there is 2 litres Borhani left in cup with capacity 3.
- For measuring 3 litres, just fill up the cup with 3 litres capacity.
- For the third branch, maximum limit is 5. Cups of capacity 1, 3, and 5 can be used.
- Now 1 to 3 litres can be measured in the previous manner.
- For measuring 4 litres, fill up the cups with capacity 1 and 3.
- For measuring 5 litres, just fill up the cup with 5 litres capacity.
