Seymour the Seal

Time limit1sMemory limit128 MB

Summary

Count herring squares reachable from S when at most 3 goo squares may be crossed between visits to a cleaner.

Level: Medium5 of 10
Topics: Graph, BFS, Shortest path
Solved: No attempts yet

Problem

Seymour the Seal is very upset. Not only did he have to witness a huge explosion while he was minding his own business and munching on some tasty herrings (and, truth be told, some of his whiskers were even singed a little), but now he has to put up with all that black, gooey stuff that burns his eyes and makes breathing so hard. Swimming certainly used to be a lot more fun. He has already figured out that travelling through too much of that gooey stuff is really bad for him, and a few times he came close to dying. Fortunately, there are some nice people on the beach who clean him off, so he needs to visit them regularly enough to reach his favourite herring hunting grounds. Alas, it seems some of his herrings are now behind so much goop that he cannot get to them at all. So Seymour wants to compute how many of his herring supplies are still reachable.

You are given a two-dimensional map of Seymour's neighbourhood. Seymour can move one square at a time, horizontally or vertically (never diagonally). Each character shows what is located at that point.

S: Seymour's seal colony (there is exactly one S on the map). Seymour starts here.
H: a herring supply.
G: black goop.
P: a spot with one of the nice seal cleaners.
.: open water.

Seymour can just barely survive swimming through 3 squares of goop; entering a 4th goop square would kill him. Visiting a cleaner washes him completely clean, so he can then survive another 3 goop squares, and he may repeat this as often as he likes. Passing through open water or herring squares does not reset the accumulated goop; only visiting a cleaner resets it.

Starting from S, determine how many herring supplies H Seymour can still reach without dying on the way.

Input

The first line contains the number $K$ of data sets. This is followed by $K$ data sets, each of the following form.

The first line contains two integers $x$ and $y$ ( $1 \le x, y \le 50$ ), the size of the map, where $x$ is the width (number of columns) and $y$ is the height (number of rows).

This is followed by $y$ lines of $x$ characters each, describing one row of Seymour's map as explained above.

Output

For each data set, first output Data Set x: on a line by itself, where $x$ is its number. Then, on the next line, output the total number of herring supplies that Seymour can still reach without dying along the way. Separate consecutive data sets with a single blank line.

Examples5

Example 1

Input

1
20 8
S.......GGGG..HHH...
GGG.....GGGGP.HHH...
HHG.HH...GGGGGGGGGGG
..G.......GGGGGGGGGG
H.G.......GGGGGGGGGG
GGGGGGGGGGGGGGGGGGGG
..GGGGGGGGGGPGGGPGGG
H.GGGG.H.PGGGPGGGGGH

Expected output

Data Set 1:
8

Example 2
Input
```
1
2 1
SH
```
Expected output
```
Data Set 1:
1
```
Example 3
Input
```
1
5 1
SGGGH
```
Expected output
```
Data Set 1:
1
```
Example 4
Input
```
1
9 1
SGGGPGGGH
```
Expected output
```
Data Set 1:
1
```
Example 5
Input
```
1
9 1
SGGG.GGGH
```
Expected output
```
Data Set 1:
0
```