Zombie Blast!
Допоможіть!!! Зомбі наступають! Почалося вторгнення зомбі, і їхній легіон на полі, наближаючись до нашої останньої лінії оборони.
Однак не все ще втрачено. В очікуванні майбутньої загрози ви розгорнули на полі бою безліч Регульованих Вогняних Мін (РВМ). Ви можете підірвати всі ці міни одночасно з єдиним радіусом вибуху, який ви контролюєте, і кожна міна миттєво спалить будь-якого зомбі в межах свого радіусу вибуху.
Ви робите супутниковий знімок, щоб отримати карту ситуації. Карта - це прямокутна область, розділена на квадратні клітини з одиничною довжиною сторони. Кожна клітина або порожня, або зайнята зомбі (Z), або зайнята міною (M). Наприклад, вона може виглядати так:
Зомбі буде спалено міною, якщо відстань між центром клітини, яку він займає, і центром клітини міни менша або дорівнює радіусу вибуху. Щоб мінімізувати побічні втрати, ви повинні підірвати міни з найменшим розміром вибуху, який все ще спалить усіх зомбі. Для даного сценарію вторгнення, яким саме є цей радіус?
Вхідні дані
Вхід починається з рядка, що містить одне ціле число N, кількість сценаріїв вторгнення (карт), для яких потрібно визначити радіус вибуху. Кожен сценарій починається з рядка, що містить два цілі числа, розділені пробілом, w і h (1 ≤ w, h ≤ 2000), що вказують ширину і висоту карти. Потім карта слідує як h рядків тексту з w символами в кожному, що вказують, що займає кожну клітину:
'Z' позначає зомбі
'M' позначає міну
'.' позначає порожню клітину.
На кожній карті буде принаймні один зомбі (Z) і одна міна (M).
Вихідні дані
Для кожного сценарію вторгнення виведіть в одному рядку дійсне число r, найменший радіус вибуху, з яким ви повинні підірвати міни, щоб спалити всіх зомбі. Ваш результат має бути точним з похибкою не більше ніж на фактор 10^{-6} відносно точного значення. (Наприклад, якщо правильна відповідь 50, будь-яка відповідь між 49.99995 і 50.00005 буде прийнята.)