Maybe, you heard the story about programmers, who pulled the rope. They wanted to reach the situation, when each programmer had competed with each other. They desire to pull the rope again. But now they want, that each pair of programmers will stand in the opposite teams at least twice.

   Number of programmers is even. They hold some rounds, and in each round all programmers divide into 2 equal teams. Programmers are very lazy :), so they want to hold as few rounds as possible. What is the minimal quantity of rounds, for which exist such schedule, that any two programmers will be in opposite teams in at least two rounds?

   For example, if we have 8 programmers, numbered from 1 to 8, then we can organize the division in the following way:

(1, 2, 3, 4) – (5, 6, 7, 8);
(1, 2, 5, 6) – (3, 4, 7, 8);
(1, 3, 5, 7) – (2, 4, 6, 8);
(1, 4, 6, 7) – (2, 3, 5, 8).

   Input

   First line of input contains the quantity of tests T (1 ≤ T ≤ 50). Each of the next T lines contains an even integer N (2 ≤ N ≤ 300) – the quantity of programmers in a current test.

   Output

   Output T lines of the form "Case #A: B", where A is the number of test (beginning from 1), B is the needed quantity of rounds for given N.

.