John loves to play computer games. He recently discovered an interesting game. In the game there are $\mathbf{N}$ cells, which are aligned in a row from left to right and are numbered with consecutive integers starting from $1$. Initially, all cells are coloured white. A cell is valid if it has white color and it does not have any adjacent red colored cell. On each turn, a player paints any valid cell with the red color. The game ends when no valid cells are present. The score of the player is equal to the number of cells they paint.

To master the game, John is practicing against a bot. The bot is poorly trained and it always paints the first valid cell from the left. John on the other hand is playing the game very carefully and he can choose any valid cell. The bot makes the first move and the players take turns alternately.

Find the maximum achievable score by the bot, assuming that John is playing optimally to minimize the score of his opponent.

Input

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The only line of each test case contains an integer $\mathbf{N}$ representing the number of cells in the game.

Output

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from 1) and $y$ is the maximum achievable score by the bot given that John is playing optimally.

Constraints

Test Set 1

$1 \le \mathbf{T} \le 6$.

$1 \le \mathbf{N} \le 6$.

Test Set 2

$1 \le \mathbf{T} \le 100$.

$1 \le \mathbf{N} \le 10^6$.

Examples

Input 1

3
1
3
6

Output 1

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

In Sample Case #1, there is $\mathbf{N} = 1$ cell. The maximum achievable score by the bot is $1$.

• First move: The bot paints the first cell with red color.

Since there are no more possible moves, so the game ends. Thus, the answer is $1$.

In Sample Case #2, there are $\mathbf{N} = 3$ cells. The maximum achievable score by the bot is $1$.

• First move: The bot paints the first cell with red color.
• Second move: John paints the third cell with red color.

Since there are no more possible moves, so the game ends. Thus, the answer is $1$.

In Sample Case #3, there are $\mathbf{N} = 6$ cells. The maximum achievable score by the bot is $2$. In this sample, there exist multiple solutions, one of them would be:

• First move: The bot paints the first cell with red color.
• Second move: John paints the third cell with red color.
• Third move: The bot paints the fifth cell with red color.

Since there are no more possible moves, so the game ends. Thus, the answer is $2$.