Zombie Blast!

Help!!! The zombies are marching! The zombie invasion has begun, and their legion is on the field, coming toward our last line of defense.

All hope is not lost, though. In anticipation of the coming doom, you have deployed a host of Adjustable Conflagration Mines (ACMs) across the battlefield. You can detonate all of these mines simultaneously with a single blast radius that you choose, and each mine instantly incinerates every zombie within its blast radius.

A satellite image gives you a map of the situation. The map is a rectangular region divided into unit square cells. Each cell is either empty (.), occupied by a zombie (Z), or occupied by a mine (M).

A zombie is incinerated by a mine if the Euclidean distance between the center of the zombie's cell and the center of the mine's cell is at most the blast radius. In other words, each zombie is destroyed only when the blast radius is at least its distance to the nearest mine. To minimize collateral damage, you must detonate the mines with the smallest blast radius that still incinerates every zombie. For a given invasion scenario, what is that radius?

The first line contains a single integer $N$, the number of invasion scenarios (maps).

Each scenario begins with a line containing two space-separated integers $w$ and $h$ ($1 \le w, h \le 2000$), the width and height of the map. Then $h$ lines follow, each with $w$ characters describing the map:

• Z denotes a zombie,
• M denotes a mine,
• . denotes an empty cell.

Every map contains at least one zombie (Z) and at least one mine (M).

For each scenario, output on its own line a single integer: the square of the smallest blast radius needed to incinerate every zombie.

That is, for each zombie compute the squared Euclidean distance to its nearest mine (if the cell-coordinate differences are $\Delta x$ and $\Delta y$, this equals $\Delta x^2 + \Delta y^2$), then output the maximum of these values over all zombies. The actual smallest blast radius is the square root of this value.

(Because the cell-coordinate differences are always integers, this squared value is always an integer. To avoid floating-point error, output the squared radius as an integer rather than the radius itself.)