Wstęp do programowania w C++

Tentaizu

Tentaizu to japońska gra umysłowa, której reguły przypominają trochę reguły popularnego sapera. Tentaizu to diagram 7 × 7, w którym dokładnie 10 spośród 49 pól to ukryte gwiazdy. Na podstawie wskazówek w postaci odkrytych liczb, należy ustalić, w których polach znajdują się gwiazdy. Liczba w polu określa, z iloma polami z gwiazdami sąsiaduje to pole poziomo, pionowo lub skośnie. Żadne pole liczbowe nie zawiera gwiazdy, ale gwiazda może zawierać się w polu, w sąsiedztwie której nie ma pól liczbowych. Jak się zapewne domyślasz, zadaniem Twoim jest napisanie programu, który rozwiąże Tentaizu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę przypadków testowych. W kolejnych wierszach znajdują się przypadki testowe. Każdy przypadek to początkowe Tentaizu, czyli diagram 7 × 7, na który składa się 7 wierszy po 7 znaków w każdym wierszu. Każe pole diagramu to albo znak kropki, albo liczba z przedziału [0-8]. Pomiędzy przypadkami testowymi znajduje się dodatkowy znak końca linii.

Wyjście
Na wyjściu wydrukuj rozwiązany diagram Tentaizu w tym samym formacie co diagram wejściowy. Rozwiązany diagram oznacza, że należy zastąpić znakiem gwiazdki dokładnie 10 pól oznaczonych znakiem kropki. Należy założyć, że każdy diagram na wejściu ma dokładnie jedno unikalne rozwiązanie. Między wydrukowanymi diagramami może znajdować się dodatkowy znak końca linii.

Przykład

Wejście
2
.....1.
....22.
.1.....
..231.1
...1...
......3
..3..2.

1....0.
.1.....
1..3...
..23.2.
..3....
.3....2
1.1..2.

Wyjście
....*1.
....22.
.1*.*..
..231.1
..*1..*
.*...*3
.*3*.2*

1....0.
*1.*...
1..3*..
..23*2.
.*3*...
*3*..*2
1.1..2*