Перетягивание каната – 2

Наверно, вы слышали историю о программистах, которые перетягивали канат. Они хотели чтобы, каждый программист посоревновался с каждым другим. Они желают поперетягивать канат снова. Но теперь они хотят, чтобы любые два программиста находились в противоположных командах по крайней мере дважды.

Количество программистов – чётное. Они проводят несколько раундов, и в каждом раунде они делятся на 2 равные команды. Программисты – очень ленивые 🙂, поэтому они хотят провести как можно меньше раундов. Какое наименьшее количество раундов, для которого существует такое распределение, чтобы любые два программиста находились в противоположных командах как минимум в двух раундах?

Например, если у нас есть $8$ программистов, пронумерованных от $1$ до $8$, то мы можем организовать деление на команды следующим образом:

• ($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$).

Входные данные

Первая строка ввода содержит количество тестов $T$ ($1\le T\le 50$). Каждая из следующих $T$ строк содержит чётное число $N$ ($2\le N\le 300$) – количество программистов в данном тесте.

Выходные данные

Выведите $T$ строк вида Case #A: B, где A – номер теста (начиная с $1$), B – нужное количество раундов для заданного $N$.

Примеры