Наверно, вы слышали историю о программистах, которые перетягивали канат. Они хотели чтобы, каждый программист посоревновался с каждым другим. Они желают поперетягивать канат снова. Но теперь они хотят, чтобы любые два программиста находились в противоположных командах по крайней мере дважды.
Количество программистов – чётное. Они проводят несколько раундов, и в каждом раунде они делятся на 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≤T≤50). Каждая из следующих T строк содержит чётное число N (2≤N≤300) – количество программистов в данном тесте.
Выведите T строк вида Case #A: B
, где A
– номер теста (начиная с 1), B
– нужное количество раундов для заданного N.