POLSKI SPOJ

Bajtocka akademia szachowa

W Bajtocji postanowiono otworzyć Akademię Szachową, której celem jest nauka Królewskiej Gry od podstaw. Kilku znanych trenerów poświęciło wiele godzin pracy, aby przygotować specjalne zadania dla początkujących adeptów.  Na początek są to proste zadania matowe: mat wieżami lub hetmanem przy pomocy króla przeciw samotnemu królowi przeciwnika. Oczywiście nie są to trudne zadania, w każdym z nich mat powstaje po nie więcej niż dwóch posunięciach białych. Niestety wskutek nieporozumienia zadania, które znalazły się w wielkiej bazie danych nie zostały właściwie oznaczone.

Twoim zadaniem jest naprawienie tego. Dla każdego zadania masz oznaczyć, ile co najmniej posunięć mają wykonać białe, aby zakończyć partię matem. Oczywiście to one zaczynają. Przyda Ci się również informacja o tym, że dawno straciły prawo do roszady.

Ściąga z reguł gry w szachy:

• Mat jest sytuacją na szachownicy, w której król przeciwnik jest atakowany przez naszą figurę i nie może znaleźć sobie bezpiecznej ucieczki oraz nie może zabić atakującej go figury. Za bezpieczne pole uznajemy takie, które nie jest atakowane przez wrogie figury.
• Dwa króle nie mogą stać na sąsiadujących ze sobą polach.
• Posunięcia wykonuje się na przemian raz białe, raz czarne.
• W naszym zadaniu zakładamy, że białe nie mają prawa do roszady.
• Rozgrywka odbywa się na szachownicy o wymiarach 8x8, linie poziome są numerowane cyframi od 1 do 8, a pionowe małymi literkami od a do h

Więcej informacji można znaleźć pod adresem: http://pl.wikipedia.org/wiki/Zasady_gry_w_szachy

Wejście:

W pierwszej linii znajduje się jedna liczba całkowita d, 1<=d<=50, oznaczająca liczbę testów.

Każdy test składa się z liczby całkowitej  n oznaczającej ilość figur na szachownicy, następnie w n kolejnych liniach podane będą położenia figur, białe figury będą oznaczone dużymi literami K- król, W- wieża, H-Hetman, mała litera k oznacza czarnego króla. Białe poza królem mogą mieć do dyspozycji jeden z następujących zestawów figur:

• Hetmana(damę)
• Jedną wieżę
• Dwie wieże

Wyjście:

Dla każdego testu należy wypisać w osobnych liniach ilość posunięć, które muszą wykonać białe, aby dać mata. Posunięcia mogą być wykonywane każdą z posiadanych figur. Możliwe odpowiedzi to: 0, 1, 2.

Przykład:

Dla danych wejściowych:

2

3

k g 8

K g 6

W f 7

3

K b 6

H d 7

k b 8

Należy wypisać:

2

1