Find the CEOs

Programming Contest for F...
Limits 1s, 512 MB

You will find millions of CEOs in this country. Some have a one page website, some have a blog built with WordPress, some have a single camera, some have YouTube channels of free medical tips and so on. Some of our political leaders think that they should attract CEOs for the sake of vote bank. Because there are two kinds of people in Bangladesh. CEOs and non-CEOs (common men like us :p) and CEOs are the majority.

Each CEO follow a rule. They will have exactly 0 or 2 employees. Employees have their own employees and they also will have exactly 0 or 2 employees. Only the employees of the lowest rank do not have any employee. I am talking about us. And if any CEO is isolated, he will not have employee. This means, if we cannot fill all the leaves of a binary tree, we must make another tree.

In sample test case 2, there are two isolated CEOs.

Now you're given MM (0<M100000 < M ≤ 10000), the total number of population, you have to find the top YY (minimum number of) CEOs who are the bosses of all of us.

Here, 1 (YY) is the boss of all CEOs. 5, 6, 8, 9, 11, 12, 14, 15 are us. And M=15M = 15.

Input

1st line of the input will contain an integer TT (1T100001 ≤ T ≤ 10000) denoting number of test cases. Each test case contains 1 integer MM (0<M100000 < M ≤ 10000).

Output

For each test case, print “Case X: Y” (without quotes) where XX is the test case and YY is the answer. Print a newline after each test case.

Sample

InputOutput
2
3
5
Case 1: 1
Case 2: 3

The boss is in Rank 1, he has 2 employees. So, If 3 is the total population, there is 1 boss.

We can get a complete tree with N=3N=3, then we need two more. We can only choose tree with 1 element. So, 3+1+1=53+1+1 = 5.


Submit

Login to submit.

Statistics

80% Solution Ratio
aminulEarliest, Aug '17
md_jakariyaFastest, 0.0s
arnob_daLightest, 131 kB
silenced.VOICEShortest, 189B
Toph uses cookies. By continuing you agree to our Cookie Policy.