Tantrix

Tantrix는 육각형 타일 56장으로 두 사람이 하는 게임이다. 타일마다 서로 다른 색 링 세 개가 그려져 있다. 두 사람은 각각 타일 다섯 장을 손에 들고 번갈아 판에 내려놓는다.

링의 색은 빨강, 초록, 노랑, 파랑 네 가지다. 모양이 같은 타일은 없고, 회전 대칭인 타일도 없다. 타일 하나는 여섯 글자 문자열로 주어진다. 위쪽 변의 링부터 시계 방향으로 각 변의 색을 적은 것이며, 대문자 R, G, Y, B가 각각 빨강, 초록, 노랑, 파랑을 뜻한다.

이 문제에서 한 수는 손에 든 타일 하나를 판의 빈 칸에 놓는 것이고, 다음 규칙을 지켜야 한다.

1. 타일은 항상 이미 놓인 타일에 붙여서 놓는다.
2. 맞닿은 두 변의 링은 색이 같아야 한다.
3. 타일 세 개 이상에 둘러싸인 빈 칸을 강제 칸이라고 한다. 손에 든 타일 하나를 강제 칸에 놓을 수 있으면 반드시 그렇게 놓아야 한다. 강제 칸이 여러 개거나 놓는 방법이 여러 가지면 그중 아무거나 골라도 된다.
4. 같은 색 링 세 개와 맞닿는 강제 칸이 생기도록 타일을 놓을 수 없다. 그런 칸에는 어떤 타일도 놓을 수 없기 때문이다.
5. 강제 칸을 따라 뻗는 두 방향의 칸을 통제 칸이라고 하며, 통제 칸에는 타일을 놓을 수 없다.

강제 칸이 하나라도 있지만 손에 든 타일을 그 어느 강제 칸에도 놓을 수 없으면, 다른 합법적인 수를 두면 된다. 규칙 4 때문에 강제 칸에 타일을 놓지 못하는 경우도 있다.

통제 칸의 정의는 이렇다. 이미 놓인 타일과 한 변이라도 맞닿은 빈 칸을 경계 칸이라고 하자. 강제 칸 F와 방향 $d$가 다음 조건을 만족한다고 하자. F의 $d$ 방향 이웃은 비어 있고, $d + 1$ 또는 $d - 1$ 방향 이웃에는 타일이 놓여 있다. 방향 번호는 타일 문자열과 같은 시계 방향 순서이며 6으로 나눈 나머지로 센다. 이때 F에서 $d$ 방향으로 한 칸씩 계속 나아가며 지나는 칸은 모두 통제 칸이다. 경계 칸이 아닌 칸이나 강제 칸에 닿으면 거기서 멈추고, 그 칸은 통제 칸이 아니다. F 둘레의 타일이 끊기지 않고 이어져 있으면 조건을 만족하는 방향 $d$는 정확히 두 개다.

이미 놓인 타일의 위치와 방향, 그리고 둘 차례인 사람이 손에 든 타일이 주어질 때 놓을 수 있는 수가 몇 개인지 세어라. 같은 타일이라도 놓는 칸이나 방향이 다르면 서로 다른 수로 센다.

첫 줄에 테스트 케이스의 수가 주어진다. 최대 50개다.

각 테스트 케이스의 첫 줄에는 이미 놓인 타일의 수 $n$이 주어진다 ($1 \le n \le 20$). 다음 $n$개의 줄에는 정수 $x$와 $y$, 그리고 여섯 글자 타일 설명이 주어진다. 설명의 첫 글자는 위쪽 변의 링 색이고 나머지는 시계 방향 순서다. 그다음 줄에는 손에 든 타일 다섯 장의 설명이 공백 하나로 구분되어 주어진다.

칸 $(x, y)$의 여섯 이웃은 위쪽 변부터 시계 방향으로 $(x, y+1)$, $(x+1, y)$, $(x+1, y-1)$, $(x, y-1)$, $(x-1, y)$, $(x-1, y+1)$이다. 타일 설명의 $i$번째 글자는 0부터 세어 이 순서의 $i$번째 이웃과 맞닿은 변의 링 색이다. 판은 무한하므로 좌표에 제한은 없다. 입력의 타일은 모두 유효하고 서로 다르며, 배치는 합법적인 게임에서 나올 수 있는 것이다. 놓인 타일 중 하나는 좌표가 0 0이다.

각 테스트 케이스마다 놓을 수 있는 수의 개수를 한 줄에 출력한다.