Forest Fires

A severe drought sharply raises the risk of forest fires. After a hot, dry summer the woods turn into tinder that ignites easily and burns quickly. In this problem you simulate how a fire spreads across a landscape and compute how long it takes for the whole wooded area to be on fire.

The landscape is a 2-D grid made of three kinds of cells:

• P — a cell with (dried) plant growth.
• . — a cell with no plant.
• F — a cell where the fire starts. There is at least one such cell.

The fire starts burning at every F cell at time $0$. From any burning cell a spark can leap to another plant or fire cell. A spark that crosses a straight-line (Euclidean) distance $d$ between two cells takes $d^2$ units of time to arrive.

Because the cost grows with the square of the distance, taking many short hops is faster than one long leap: crossing a distance $d$ one cell at a time costs only $d$, while jumping the whole distance $d$ at once costs $d^2$. Fire therefore races through dense growth but is slowed by wide gaps, where it must rely on a spark luckily flying far. A cell marked . has no plant and never burns.

For each landscape, report the earliest time at which every cell that is not . is burning.

The first line contains the number $K$ of data sets. Each of the $K$ data sets has the following form:

• A line with two integers $h$ and $w$ ($1 \le h, w \le 20$): the height and width of the map.
• $h$ lines follow, each with exactly $w$ characters. Every character is P, F, or ..

For each data set, print a line Data Set x:, where $x$ is the data set's number (starting from 1). On the next line print the earliest time at which every cell not marked . is burning. Print a blank line between consecutive data sets.