Rope pulling – 2

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 number of tests $T$ ($1\le T\le 50$). Each of the next $T$ lines contains an even integer $N$ ($2\le N\le 300$) – the number of programmers in a current test.

Output

Ouput $T$ lines of the form Case #A: B, where A – is the number of test (staring at $1$), B – the needed quantity of rounds for given $N$.

Examples