AlgoLiga 2018

Problem ośmiu hetmanów

Na podstawie aktualnej sytuacji na szachownicy 8×8, rozstaw za pomocą minimalnej liczby ruchów (zgodnych z zasadami gry w szachy) osiem hetmanów tak, aby wzajemnie nie atakowały się.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych n (n ≤ 500).
Każdy przypadek testowy to aktualna sytuacja na planszy z ośmioma hetmanami, na którą składa się osiem wierszy po osiem znaków w każdym. Znak "." oznacza puste pole, znak "H" to pole zajęte przez hetmana. Pomiędzy przypadkami testowymi znajduje się jedna pusta linia.

Wyjście
Dla każdego przypadku testowego należy podać minimalną liczbę ruchów prowadzących do rozwiązania problemu.

Przykład

Wejście

2
......H.
...H....
.H......
....H...
.......H
H.......
..H.....
.....H..

H.......
.H......
..H.H...
........
...H..H.
.H......
........
...H....

Wyjście
0
6