eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Железный дровосек и мишки Гамми

Железный дровосек и мишки Гамми

Лимит времени 10 секунд
Лимит использования памяти 64 MiB

На одном из популярных интернет-ресурсов с завидной регулярностью происходит нашествие злобных мишек Гамми. Попав на ресурс, они все как один начинают по команде вожака голосовать "за" (+) или "против" (-) всех сообщений подряд. Понимая, что их проделки могут быть обнаружены, а сами они наказаны, мишки Гамми на ресурсе маскируются. Для этого каждая пара мишек Гамми создаёт виртуального пользователя и прикрепляет к нему аватар добродушного плюшевого медведя, поэтому всем пользователям кажется, что голосуют не мишки Гамми, а плюшевые медведи.

В разных сообщениях обитатели портала могут голосовать по разному, но в одном сообщении мнение всех проголосовавших одинаковое.

Железный дровосек, будучи привыкшим к определённому порядку, решил наказать проказников. Для этого ему нужно для начала определить, какой максимальной численности клика мишек Гамми находилась в наблюдаемое время на ресурсе. Помогите ему в этом.

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

В первой строке задано натуральное число t - количество тестовых случаев, не превышающее 100. Далее идёт 2t строк, где сначала в первой строке указывается количество активных новых сообщений за наблюдаемый период n (1n10^5), а в следующей строке - рейтинг соответствующего сообщения r_i (r_i|2·10^9|) на момент просмотра.

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

Для каждого тестового случая выведите в отдельной строке соответствующее решение задачи в формате, указанном в примере выходных данных.

Пример

Входные данные #1
2
2
3 4
5
-7 6 12 -13 9
Выходные данные #1
Case 1: 3
Case 2: 4