Sofdor Ali is one of the most famous scientists of Bangladesh. He is also well known for his puzzle solving skill. One day after he finished his seminar one man came to him and challenged him to solve a puzzle. Sofdor Ali was surprised with such bold approach of that man facing the greatest mind of Bangladesh. Anyway, the puzzle was that you have a weight of 40 units. You can break this weight to smaller integer weights. And you are provided with a weighing scale. Now you are to find the minimum number of weight pieces you need to make from the 40 units weight in order to measure any integer weight from 1 to 40. You can use both pans of the balance to measure given weight.
Great Sofdor Ali gave it a thought for a moment and said “I can do it and I can generalize my solution for initial weight N instead of 40. But can you do it for N?” The young challenger was astonished. He tried to do it but couldn’t generalize his solution of 40 units. So he gave the problem to you.
You are given a weight N. Find out the minimum number of pieces we need to make for measuring any weight between 1 to N inclusive.
First line of input contains an integer T (0 < T ≤ 104) representing the number of test cases. Next T line each contains an integer N (0 < N ≤ 1018).
For each case print Case i: ans in a line where i is the case number and ans is our desired answer.
| Input | Output |
|---|---|
3 40 6 15 | Case 1: 4 Case 2: 3 Case 3: 4 |
For the first case we’ll make 4 weights equal to 1, 3, 9, 27. 1+3+9+27=40. With this weights we can measure any weight between 1 and 40. Say we will measure 29 units weight. So we put our object the on right pan and 1 unit weight on right pan. On the left pan we put 3 and 27.
For 3rd case we’ll divide our weight in 1, 2, 3, 9 units.