Tantrix

Tantrix is a two player game played with 56 hexagonal tiles. Each tile carries three links in different colours. Both players hold five tiles and take turns placing them on the playing field.

There are four link colours: red, green, yellow and blue. No two tiles are identical, and no tile is rotation symmetric. A tile is described by a six letter string that lists the link colours in clockwise order, starting with the link on the upward side. The uppercase letters R, G, Y and B stand for red, green, yellow and blue.

A move places one tile from the hand on an empty space, subject to these rules:

1. A tile must always be placed next to tiles already played.
2. The links in all touching tiles must match colour.
3. An empty space surrounded by three or more tiles is called a forced space. If the player can place one of the tiles in hand in a forced space, that move must be made. If there are several forced spaces, or several ways to place a tile in one, any of them may be chosen.
4. It is not allowed to place a tile so that a forced space is created containing three links of the same colour, since no tile could ever be placed there.
5. The two sides along a forced space are called controlled sides, and no tile may be placed on a space that lies on a controlled side.

If there is at least one forced space and no tile in hand can be placed in any of them, the player makes any other legal move. Rule 4 on its own can be what keeps a tile out of a forced space.

Controlled sides are defined as follows. Call an empty space that touches at least one played tile a border space. Let F be a forced space and let $d$ be a direction such that the neighbour of F in direction $d$ is empty while the neighbour in direction $d + 1$ or $d - 1$ holds a tile. Direction numbers follow the same clockwise order as the tile strings and are taken modulo 6. Step from F in direction $d$ and keep stepping the same way: every space entered is controlled. The walk stops at the first space that is not a border space or that is itself a forced space, and that space is not controlled. When the tiles around F form one unbroken run, exactly two directions $d$ qualify, which is why they are the two sides along the forced space.

Count the legal moves available to the player to move, given the position and orientation of the tiles already played and the tiles in hand. If a tile can be placed on several spaces, or in several orientations, each such combination counts as a distinct move.

The first line contains the number of test cases, at most 50.

Each test case begins with a line containing an integer $n$ ($1 \le n \le 20$), the number of tiles that have already been played. The next $n$ lines each contain two integers $x$ and $y$ followed by a six letter tile description. The first character of the description belongs to the link on the upward side, and the remaining colours follow clockwise. After them comes one line with the descriptions of the five tiles in hand, separated by single spaces.

The six neighbours of the space $(x, y)$, starting from the upward side and continuing clockwise, are $(x, y+1)$, $(x+1, y)$, $(x+1, y-1)$, $(x, y-1)$, $(x-1, y)$ and $(x-1, y+1)$. Character $i$ of a tile description, counting from 0, gives the colour of the link on the side shared with neighbour $i$ in that order. The playing field is infinite, so the coordinates are not restricted. All tiles in the input are valid and distinct, and the layout is a position that could have arisen from a legal game. One of the played tiles has coordinates 0 0.

For each test case, output a single line containing an integer: the number of legal moves.