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