Паркан
Містер Докмай — садівник, який вирощує рідкісні та дорогі квіти на прямокутній ділянці землі, розділеній на секції з M рядків і N стовпців. Через часті крадіжки він побудував паркани для захисту своїх квітів. Оскільки квіти мають різну вартість, деякі секції захищені краще.
На жаль, з часом паркани почали руйнуватися. Щоб оцінити поточний стан, пан Докмай створив карту, де кожній секції землі відповідає число. На цій карті одиниця означає, що секція має паркан, а нуль — що секція не має паркану і підходить для посадки. Рисунок 1 ілюструє приклад карти з 11 рядків і 12 стовпців.
Рисунок 1. Ілюстрація ділянки землі для посадки квітів.
Злодій може проникнути на ділянку з будь-якої зовнішньої секції (показаної на Рисунку 1). Якщо секція має паркан, злодій повинен прорізати його, щоб увійти. Як тільки він потрапляє на ділянку, йому може знадобитися прорізати ще більше парканів, щоб дістатися до певної секції. Це може вимагати значних зусиль, якщо потрібно прорізати кілька парканів.
Припустимо, що злодій може переміщатися з однієї секції в іншу, суміжну з нею горизонтально або вертикально, але не по діагоналі. Наприклад, якщо він знаходиться в секції на Рядку 5 Стовпець 7, він може переміститися в секції на Рядку 4 Стовпець 7, Рядку 6 Стовпець 7, Рядку 5 Стовпець 6 або Рядку 5 Стовпець 8. Однак, він не може переміститися в секцію на Рядку 4 Стовпець 6.
Рівень безпеки секції визначається як мінімальна кількість прорізів паркану, які злодій повинен зробити, щоб увійти в секцію. Наприклад, рівень безпеки секції на Рядку 6 Стовпець 6 дорівнює 2, на Рядку 4 Стовпець 5 — 1, а на Рядку 1 Стовпець 3 — 0. Індекси рядків і стовпців починаються з 1.
Пан Докмай планує посадити дуже дорогі квіти, тому шукає найбільш захищені секції. Він також хоче знати кількість секцій з найвищим рівнем безпеки. Врахуйте, що тільки секції, позначені 0 на карті, підходять для посадки квітів. Пан Докмай не планує знімати паркани для створення нових секцій для посадки.
Ваше завдання — написати програму, яка визначає найвищий рівень безпеки та кількість секцій з цим рівнем безпеки.
Вхідні дані
Перша лінія введення містить кількість тестових випадків T ≤ 10. Цілі числа в одному рядку розділені пробілом.
Перша лінія кожного тестового випадку містить два цілі числа R і C (5 ≤ R, C ≤ 1000). Перше число — кількість рядків R, друге — кількість стовпців C карти секцій.
Рядки з 2 по R+1 містять дані секцій кожного рядка, від Рядка 1 до Рядка R. Кожен рядок містить C цілих чисел, де 0 представляє секцію, придатну для посадки квітів, а 1 — паркан.
Примітка: карта завжди має принаймні одну секцію, придатну для посадки квітів. Якщо ви використовуєте мову програмування Java, рекомендується використовувати BufferedReader та StreamTokenizer для читання вхідних даних.
Вихідні дані
Для кожного тестового випадку виведіть 2 цілі числа. Перше — невід'ємне число, що показує найвищий рівень безпеки секції землі, придатної для посадки квітів. Друге — кількість секцій з цим рівнем безпеки. Два числа розділені пробілом.
Пояснення: Для обох прикладів зірочки нижче представляють секцію з найвищим рівнем безпеки. Товсті підкреслені числа показують деякі з шляхів, якими злодій може пройти в секцію з найвищим рівнем безпеки, прорізавши найменшу кількість парканів.