Tuenti Challenge 7

Challenge 3 - Board games

numbers

You can't lie to us, we know you love board games... you absolutely love them, and we also know that you are tired of the typical point counting method.

We need a cool system for counting points for our brand new board game, and we think we could use cards to do it. For example, a score of 10 could be represented with the set of cards 7 and 3. But those fancy printed cards don't come cheap and that's why we need you!

We want to know how many cards we need to print, given a maximum possible score. We don't want our board game to have repeated cards, so you need to tell us the size of the smallest set of cards that, for any number from 1 to P, we can find a subset of those cards whose sum equals that number, being P the maximum score of the game.

Input

The first line will contain an integer C, the number of cases for our problem.
Each case consists of a line with the integer P, the maximum points you need to be able to count.

Output

For each case, a line starting with "Case #x: " followed by the size of the minimum set of cards needed for the score P.

Examples

Case 1:

1
Case 2:

6
Case 3:

3

In Case 1, we need a card with 1.
In Case 2, we can count up to 6 with only 3 cards, for example 1, 2 and 3.
In Case 3, we need the cards 1 and 2.

Limits

  • 1 ≤ C ≤ 104
  • 1 ≤ P ≤ 109

Sample Input

3
1
6
3

Sample Output

Case #1: 1
Case #2: 3
Case #3: 2

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want to. Be careful with extra whitespaces, the output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).

If you have any doubts, please check the info section.