Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SZACH123 - Szachowe możliwości

 

Najpierw liczba naturalna t określająca ilość zestawów danych. W pierwszej linii każdego zestawu danych liczby n i m (n,m -liczby naturalne i 1 <=n,m <= 26) oddzielone spacją. Następnie nieznana ilość bierek w postaci BIERKA x0 y0 (BIERKA - jedna z liter: W, H, S, G, P, K odpowiadająca danej bierce szachowej; x0 - mała litera alfabetu angielskiego; y0 - liczba naturalna 1<= y0 <= 26). Na końcu każdego zestawu jeden wyraz TAK/NIE informujący o tym, czy król robił już roszadę. Roszada jest możliwa tylko wtedy gdy król stoi na polu E1, pomiędzy nim a wieżą stojącą w rogu nie ma żadnej bierki oraz gdy otrzymamy NIE dla danego zestawu. Jeżeli króla nie ma na szachownicy wtedy zawsze zejdzie: TAK
Można przyjąć, że żadne dwie bierki nie stoją na tym samym polu oraz ruch można wykonać tylko na pole, które nie jest zajęte przez żadną bierkę.

typical_board

Na szachownicy o wymiarach n x m rozstawione są bierki tylko jednego, białego, koloru. Znając tylko wymiar, rozstawienie bierek oraz fakt że nie rozważamy ruchu roszady (król nie ma takiego ruchu), określ na ile sposobów można wykonać najbliższy ruch.

O tym jak poruszają się poszczególne bierki można przeczytać tutaj: https://pl.wikipedia.org/wiki/Zasady_gry_w_szachy

Uwaga: jako, że bierki należą do jednego koloru, to króle nie szachują się nawzajem (mogą stanąć obok siebie).

Input

Najpierw liczba naturalna t określająca ilość zestawów danych. W pierwszej linii każdego zestawu danych liczby n i m (n, m -liczby naturalne i 1 <=n,m <= 26) oddzielone spacją. Następnie nieznana ilość bierek w postaci BIERKA x0 y0 (BIERKA - jedna z liter: W, H, S, G, P, K odpowiadająca danej bierce szachowej; x0 - mała litera alfabetu angielskiego; y0 - liczba naturalna 1<= y0 <= 26). Uwaga: na szachownicy może być dowolna ilość dowolnych bierek (w tym także np. trzy króle).

Można przyjąć, że żadne dwie bierki nie stoją na tym samym polu oraz ruch można wykonać tylko na pole, które nie jest zajęte przez żadną inną bierkę (zgodnie z zasadami szachowymi).

Output

Jedna liczba określająca ile można dokonać ruchów.

Example

Input:
5
3 3
S a 1
G b 3
W b 2
1 2
W a 2
8 8
G h 8
8 8
K e 1
W a 1
W b 2
7 5
S g 1
S c 5
G f 1
G b 3
G d 3
G e 4
G b 5
P g 2
P f 3
Output:
6
1
7
29
20

Dodane przez:Karol Kurek
Data dodania:2017-10-11
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.