Oil Exploration

Before oil can be extracted, someone first has to find it. Oil companies want to find oil they can extract as cheaply as possible. A major part of the price is how deep, and through what material, one must drill before reaching oil. For this problem the size of the oil reservoir is ignored. Given a map of the seafloor, compute the cost of drilling at each position.

The first line contains the number of data sets $K$. Then $K$ data sets follow, each in the format below.

The first line of each data set contains two integers $h$ and $w$ ($1 \le h, w \le 40$): the height and width of the seafloor map. This is followed by $h$ lines, each a string of $w$ upper-case letters. Each letter is one of:

• X: oil is present at that location
• H: hard rock
• S: soft rock

Drilling through one cell of hard rock costs $3$, and through one cell of soft rock costs $1$. For each of the $w$ columns, drill straight down from the top and compute the total cost until the first oil is reached. Some columns may contain no oil at all; for those, output the letter N instead of a cost.

For each data set, first output a line of the form Data Set x:, where $x$ is the data set's number (starting from 1). On the next line, output the $w$ drilling costs from left to right, separated by a single space (with no trailing space). For a column with no oil, output N. Print a blank line between the outputs of two consecutive data sets (there is no blank line after the last data set).