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