Flood-It
Flood-It — це популярна гра для одного гравця на багатьох смартфонах. Гравцеві надається n×n дошка з плитками, де кожна плитка має один з 6 кольорів (пронумерованих від 1 до 6). Кожна плитка може бути з'єднана з максимум 4 сусідніми плитками в напрямках Північ, Південь, Схід і Захід. Плитка вважається з'єднаною з початковою (плитка у верхньому лівому куті), якщо вона має такий самий колір, як і початкова, і існує шлях до початкової плитки, що складається лише з плиток цього кольору.
Гравець робить хід, вибираючи один з 6 кольорів. Після вибору всі плитки, з'єднані з початковою, змінюються на обраний колір. Гра триває, поки всі плитки не стануть одного кольору. Мета гри — змінити всі плитки на один колір, бажано з найменшою кількістю ходів.
Доведено, що знайти оптимальні ходи — дуже складна задача. Для цієї задачі ви будете моделювати дуже просту жадібну стратегію, щоб побачити, наскільки добре вона працює:
для кожного ходу вибирайте колір, який призведе до найбільшої кількості плиток, з'єднаних з початковою;
якщо є нічия, розв'язуйте її, вибираючи колір з найменшим номером.
Щоб проілюструвати це, розглянемо перший тестовий випадок у зразку введення, початкова дошка виглядає так:
Якщо ми виберемо колір 3 для першого ходу, результат буде таким:
де плитки, з'єднані з початковою, заштриховані. У наступному ході ми вибираємо колір 4, оскільки можемо збільшити кількість плиток, з'єднаних з початковою, на 5 плиток:
Вхідні дані
Вхід складається з кількох тестових випадків. Перша строка введення — це одне ціле число, не більше 20, що вказує на кількість тестових випадків, які слідують. Кожен випадок починається з рядка, що містить ціле число n (1 ≤ n ≤ 20). Наступні n рядків кожен містить n символів, що дають початкові кольори n×n дошки з плитками. Кожен колір вказується цифрою від 1 до 6.
Вихідні дані
Для кожного випадку виведіть два рядки виходу. Перший рядок вказує кількість ходів, необхідних для зміни всіх плиток на один колір. Другий рядок вказує 6 цілих чисел, розділених одним пробілом. i-те число вказує кількість разів, коли колір i обирається як хід у грі.