POLSKI SPOJ

Kiedy można wziąć króla, to się nazywa szach, kiedy on już nie ma się gdzie podziać, to jest mat.

Taką definicję szacha oraz mata przedstawił Vladimir Nabokov, rosyjski pisarz hobbystycznie układający zadania szachowe. Na przestrzeni lat tego typu zadania stały się niemal odrębną dziedziną tej gry, a osoby które zajmują się ich układaniem uzyskały miano problemistów. Jedną z dziedzin problemów szachowych są kompozycje szachowe. Jest to sztuczny układ figur, zwykle gra ogranicza się do kilku ruchów, a jej celem jest uniknięcie przegranej. Jedną z odmian kompozycji szachowej jest studium - zadanie przypominające końcową część partii. Tego typu sytuację ułożyliśmy - zostałeś na polu bitwy wyłącznie z królem, a Twój przeciwnik posiada jeszcze całkiem sporą armię. Scenariusz jak na koniec partii szachowej raczej mało prawdopodobny, co nie zmienia faktu, że jest on możliwy (pomijając jeden drobny szczegół - przeciwnik nie posiada króla). Grasz białymi figurami i jest właśnie Twój ruch. Interesuje nas czy istnieje takie pole, na które przesunięcie króla pozwoli przedłużyć partię.

Gra rozgrywa się na szachownicy o wymiarach 8 × 8. Twój król oznaczony jest jako litera K, możliwe figury przeciwnika to:

• P - pion (maksymalna liczba 8, poruszają się w kierunku od 8 do 1)
• W - wieża (maksymalna liczba 2)
• S - skoczek (maksymalna liczba 2)
• G - goniec (maksymalna liczba 2)
• H - hetman (maksymalna liczba 1)

Napisz program, który zwróci SZACH albo MAT, w zależności od sytuacji w jakiej się znajdujesz. Jeżeli istnieje pole, na które możesz bezpiecznie się przemieścić (analizujemy sytuację wyłącznie po Twoim ruchu) wypisz SZACH. Jeżeli nie ma możliwości przesunięcia króla na pole, na którym nie zostanie zbity przez przeciwnika w pierwszym jego ruchu wypisz MAT. Lewy dolny róg szachownicy oznaczony jest jako 1 A.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 30) określająca liczbę zestawów danych.

Pierwszą linię każdego zestawu stanowi liczba S (1 ≤ S ≤ 16) określająca liczbę figur na szachownicy (łącznie z Twoim królem). W kolejnych S liniach znajdują się opisy figur. Każdy opis składa się z liczby N (1 ≤ N ≤ 8) oraz wielkiej litery (A do H) opisujących pozycję figury oraz z litery określającej jej rodzaj.

Wyjście

Dla każdego zestawu danych należy wypisać w osobnej linii słowo SZACH jeżeli jest możliwość wykonania bezpiecznego ruchu albo słowo MAT w przeciwnym wypadku.

Przykład

Wejście:

2
4
8 H G
6 B H
5 D K
1 E W
6
5 D S
5 G S
5 H G
3 F K
2 A W
1 G H

Wyjście:

SZACH
MAT