Problem C
Dacey the Dice

Dacey the Dice is lost in the twisted forest and needs help to find a way back home. Dacey the Dice moves by rolling over from one side to the next along dark and petrifying pathways. Dacey’s goal is to make a safe return to Dacey’s Home Sweet Home, which is a safeguarded by a magnetic door.

The twisted forest is laid out as an $N\times N$ grid, where each of the $N^2$ locations corresponds to an intersection in the forest. Dacey starts his frightful journey at one of the $N^2$ locations with $1$ dot at the top and $2$ dots facing right. This implies there are $6$ dots at the bottom, $5$ dots facing left, $4$ dots facing upwards, and $3$ dots facing downwards. (Note that the two numbers of opposite faces of a die always add up to $7$. Also, the only side that you cannot see is the bottom.) Every dot on Dacey the Dice contains a powerful magnet.

Dacey’s Home Sweet Home is underground and is located at one of the $N^2$ intersections. Dacey’s Home Sweet Home is secured by a door containing four magnets. The magnetic door will only open when Dacey is standing on top of the door with the side with five dots facing downwards. If Dacey stands on the door with any other side facing downwards, the door won’t open, but Dacey can still move past.

Some of the $N^2$ locations are occupied by a wicked gigantic magnet which, if ever stepped on by Dacey, immediately will turn Dacey into a petrified immovable monument. Dacey’s initial location and Dacey’s Home Sweet Home are never occupied by a wicked gigantic magnet.

Dacey the Dice can only move by rolling over, which changes both Dacey’s position and orientation. For example, if Dacey has $1$ dot at the top and $2$ dots facing left, and rolls right to the adjacent location, Dacey will afterwards have $1$ dot facing right and $2$ dots at the top. It takes exactly one roll to move between two adjacent locations. Dacey cannot roll diagonally and cannot roll outside the twisted forest.

Your task is to determine whether Dacey can reach the comfort of the inside of Dacey’s Home Sweet Home or not.

Input Format

The first line contains a single integer $T\le 100$ giving the number of test cases. Each case starts with a line containing an integer $N$ ($2\le N\le 20$), the length of the sides of the twisted forest. The next $N$ lines containing $N$ characters each, describing the twisted forest. Each location in the forest is described by one of the following characters:

• . – Normal location

• * – Wicked gigantic magnet

• S – Dacey’s initial location

• H – Dacey’s Home Sweet Home

There will be exactly one cell for Dacey’s initial location, and exactly one cell for Dacey’s Home Sweet Home.

Output Format

For each test case, output a single line with “Yes” if Dacey can successfully can get inside Dacey’s Home Sweet Home, or “No” otherwise.

5
2
*.
HS
2
*.
SH
2
S.
.H
3
S..
...
..H
3
S..
***
..H

Yes
No
No
Yes
No