POLSKI SPOJ

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