Challenge 3 - Board games


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. 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 how many unique cards are needed in order to be able to sum all the numbers from 1 to P, being P the maximum score of the game.


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.


For each case, a line starting with "Case #x: " followed by the minimum number of cards required to count from 1 to P.


Case 1:

Case 2:

Case 3:


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


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

Sample Input


Sample Output

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