Problem C: Świnka skarbonka

Treść

Rodzice małej Basi postanowili nauczyć córkę oszczędności. Aby oszczędzanie nie było kolejnym nudnym obowiązkiem, tato skonstruował specjalną chrumkającą świnkę skarbonkę. Przy każdym wrzuceniu monety świnka mruga oczkami i wydaje pełen zadowolenia odgłos. Gdy przez dłuższy czas Basia zapomni nakarmić zwierzątko pieniążkiem, świnka staje się niegrzeczna: głośno kwiczy i rozrzuca naokoło wszystkie zabawki.

Oprócz elementów typowo zabawowych tato Basi umieścił w śwince specjalną minidrukarkę, która co jakiś czas drukuje bieżący stan oszczędności, umożliwiając w ten sposób śledzenie postępów córki. Tato chciałby teraz wprowadzić dane do komputera aby móc przeprowadzić bardziej skomplikowane analizy, a ich wyniki przedstawić za pomocą atrakcyjnych wizualnie wykresów. W tym celu zeskanował wydruki i już miał się brać do dalszej pracy, gdy uświadomił sobie, że skaner utworzył plik graficzny, a on potrzebuje tekstu, który może wkleić do arkusza kalkulacyjnego. Na szczęście przypomniał sobie, że w sąsiedztwie mieszka pewien zdolny programista, czyli Ty. Pomóż tacie Basi i napisz program, który bezużyteczny obraz ze skanera zamieni na jak najbardziej użyteczny ciąg cyfr.

Po przeanalizowaniu kilku zeskanowanych kartek udało Ci się zidentyfikować wzorce poszczególnych cyfr:

................................
..***....*...***....***......*..
.*...*..**..*...*..*...*....**..
.*...*...*......*......*....**..
.*...*...*.....*.....**....*.*..
.*...*...*....*........*...*.*..
.*...*...*...*.........*..*****.
.*...*...*..*......*...*.....*..
..***....*..*****...***.....***.
................................

...................................
.*****....**...*****...***....***..
.*.......*.....*...*..*...*..*...*.
.*......*..........*..*...*..*...*.
.****...****.......*...***...*...*.
.....*..*...*.....*...*...*...****.
.....*..*...*.....*...*...*......*.
.*...*..*...*....*....*...*.....*..
..***....***.....*.....***....**...
...................................

Teraz nie pozostaje już nic innego jak tylko zabrać się za programowanie.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera dwie liczby całkowite w oraz s (1<=w,s<=500), oddzielone spacją, oznaczające odpowiednio wysokość i szerokość zeskanowanej kartki. W kolejnych w wierszach znajduje się wynik skanu. Każdy z tych wierszy zawiera dokładnie s znaków, przy czym . (kropka) oznacza, że w danym punkcie kartka jest biała, a * (gwiazdka) oznacza czarną kropkę tuszu naniesioną przez drukarkę.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest ciąg rozpoznanych cyfr lub znak . (kropka) gdy na kartce nie znajduje się żadna cyfra. Rozpoznane cyfry należy podawać bez odstępów, w kolejności występowania od góry do dołu i od lewej do prawej. Cyfrę uznajemy za rozpoznaną, gdy jej krawędź idealnie pokrywa się ze wzorcem i nie sąsiaduje (w najbliższych punktach w osi poziomej, pionowej i po skosach) z żadnymi innymi kropkami tuszu.

Przykład

dane wejściowe:
2
11 30
...........................*..
..***....*...***..***.....**..
.*...*..**..*...**...*....**..
.*...*...*......*....*...*.*..
.*...*...*.....*...**....*.*..
.*.*.*...*....*......*..*****.
.*...*...*...*.......*.....*..
.*...*...*..*....*...*....***.
..***....*..*****.***..*......
......**...............***....
...******............****.....
10 10
..........
..........
.*....*...
..........
..*..*....
..........
...**.....
...**.....
....*.....
...***....

wynik:
401
.