Tuenti Programming
Challenge 2

Go to tuenti

  Home  Info  Questions  Stats       

Challenge 2: The binary granny « Prev Next »


Completion time: min: 0:15 h
10 percentile: 0:47 h
90 percentile: 24:05 h
max: 133:54 h
Submit exec time: min: 0.21 s
10 percentile: 0.70 s
90 percentile: 4.26 s
max: 41870.53 s
Test tries: min: 1
10 percentile: 1
90 percentile: 19
max: 139
# of completions:312

Yuki is a lucky girl. Her grandma Chika is a lovely old lady, owner of a sheep farm, expert baker and knitting ninja, and has a hazelnut tree in her backyard. Yuki is always craving the super tasty hazelnuts that can be picked from it and asking for more and more. But her grandma is a wise woman and she doesn’t want to spoil Yuki or to make her sick with all the hazelnuts she can eat.

Chika is quite a fan of binary numbers and uses base 2 for everything (and I can assure you she has never been cheated when buying groceries). She came up with the following simple game for Yuki: she would say a number N and Yuki would choose two numbers, x and y, such that x + y = N. Then Chika would give Yuki as many hazelnuts as the sum of the number of ones of x and y in base 2. For example, if Chika chooses 7 and Yuki picks 3 and 4, then she will get 2 (as 3 in base 2 is 11) plus 1 (since 4 in base 2 is 100): 3 hazelnuts.

Yuki wants to know what the maximum number of hazelnuts that she could get from Chika.

Input

The first line of the input gives the number of test cases, C, and C test cases follow. Each test case consists of a line with an integer N, 0 ≤ N.

Output

For each test case, output one line containing "Case #x: M", where x is the case number (starting from 1) and M is the maximum number of hazelnuts that Yuki can get from her binary grandmother.

Limits:

1 ≤ C ≤ 2000
Test dataset: N ≤ 104
Challenge dataset: N ≤ 1019 (may not fit in a 32 bit integer)

Sample input

3
1
6
2135

Sample output

Case #1: 1
Case #2: 4
Case #3: 14