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