Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Find the CEOs

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 :D . 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 M (Total number of population, 0 < M ≤ 10000). You have to find the top Y (minimum number of) CEOs who are the bosses of all of us. Image credit : Wikipedia Author : Qwertyus

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

Input

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

Output

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

Sample

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

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

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


Discussion
Statistics

80% Solution Ratio

aminulEarliest, Aug '17

md_jakariyaFastest, 0.0s

arnob_daLightest, 131 kB

SIR.24Shortest, 324B

Submit

Login to submit