Tuenti Challenge 6

Challenge 1 - Team Lunch

Today is our bi-weekly team lunch! This time, we're going to our favorite Indian restaurant and we want to know in advance the minimum number of tables required to seat all the team members.

All the tables are square shaped, they must always be joined in a row and there can be no more than one diner seated at each side of a table.

Example for 4 diners:

     O
   +---+
 O | 1 | O
   +---+
     O

4 diners -> 1 table

Example for 5 diners:

     O   O
   +---+---+
 O | 1 | 2 |
   +---+---+
     O   O

5 diners -> 2 tables

Input

In the first line, an integer T indicates the number of cases. Each case is described in a line with an integer N indicating the number of diners.

Output

For each case t, the output is the string Case #t: r where t is the case number and r is the result.

Limits

1 <= T <= 50

0 <= N <= 2^16

Sample Input

4
4
6
5
3

Sample Output

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

NOTE: Take into account that apart from submitting the correct solution as soon as possible, code quality is also important as it will be reviewed if you end up in the top of the ranking.

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.