C Programming Language

Problem Title: Worst Case Scenario

Red is a pokemon trainer from Pallet Town who wish to become a pokemon master one

day. To achieve that, he needs to defeat all pokemon gyms. Currently, Red is in Ver- million City to challenge the gym leader in that city. Lt.Surge, as the Vermillion City

gym leader, decided to make the gym challenge a little bit harder by giving a small puzzle. Suppose that there are N electrical currents blocking the passage to a room. At the same time, there are N buttons where each button deactivates one electrical current when pressed in the right order. Unfortunately, if one button is pressed in the wrong order, all the currents will turn back on. To make the challenge easier to solve, the order of the button stays the same even after the wrong button is pressed.

Red really wants to win the gym challenge and therefore ask you, as his friend, to design an optimal algorithm to solve the problem. Once you know the algorithm, Red wants to know the minimum number of button presses he needs to make on the worst case scenario.

Format Input

Input consists of an integer T as the number of test case. Each test case consists of one integer N - number of button.

Format Output

Output should be expressed in format Case #X: Y - X is the number of the query, and followed by one integer Y , minimum number of button presses on the worst case scenario.

Constraints

1 T 100 1 N 100000

Sample Input & Output (standard input & output)

3

3

Case #1: 7

22

Case #2: 1793

222

Case #3: 1823693

Explanation For example if there were 3 buttons, in the correct order of A B C. One worse case scenario might be: C B A C A B C. Which means he has to press 7 buttons in order to unlock the puzzle.