C - Gońce

Szachy to gra rozgrywana na planszy składającej się z 8 poziomych rzędów i 8 pionowych kolumn.

Goniec to jedna z figur szachowych. Na szachownicy bez innych figur goniec atakuje wszystkie pola po przekątnych pól względem pola, na którym stoi. Jeżeli na którejś przekątnej znajduje się inna figura, to goniec atakuje tylko te pola, które znajdują się między nim, a tą figurą (włącznie z polem zajmowanych przez tę figurę).

Kolejną figurą jest król. Król w jednym ruchu może poruszyć się o jedno pole w dowolnym kierunku (także po przekątnej). Jeżeli na tym polu znajduje się inna figura, to król bije (usuwa) tę figurę.

Na szachownicy znajduje się król i pewna liczba wrogich gońców. Początkowe pole zajmowane przez króla nie jest atakowane przez żadnego gońca. Napisz program, który obliczy minimalną liczbę ruchów króla potrzebnych do zbicia wszystkich gońców. Zakładamy, że gońce nie poruszają się. Król nie może przechodzić przez pola atakowane przez niezbite gońce.

Wejście

W pierwszej linii znajduje się liczba testów [asciimath]T (1<=T<=20)[/asciimath]. W kolejnych liniach znajduje się  [asciimath]T[/asciimath] zestawów testowych.

Pojedynczy zestaw testowy składa się z 8 linii. Każda z nich opisuje kolejny rząd pól szachownicy. Pojedyncza linia opisu zawiera 8 znaków. Możliwe znaki to:

  • K - oznacza pole z królem
  • G - oznacza pole z gońcem
  • . - oznacza puste pole

Każdy opis szachownicy jest zgodny z treścią zadania.

Wyjście

Dla każdego zestawu testowego należy wypisać jedną liczbę - minimalną liczbę ruchów króla potrzebnych do zbicia wszystkich gońców lub [asciimath]-1[/asciimath] jeżeli jest to niemożliwe.

Przykład

Wejście:
4
G.K.....
........
........
........
........
........
.......G
........
.GGGGGGG
G.GGGGGG
GG.GGGGG
GGG.GGGG
GGGG.GGG
GGGGG.GG
GGGGGG.G
GGGGGGGK
..KG....
........
........
........
.......G
........
........
........
KGGGGGGG
........
........
........
........
........
........
........

Wyjście:
13
-1
-1
7

Objaśnienie przykładu:

Na pierwszej szachownicy przez "L" oznaczone są pola atakowane przez lewego gońca, a przez "P" przez prawego. Król musi najpierw zbić gońca po prawej stronie, żeby móc zbić gońca po lewej stronie.

GPK.....
.LP.....
..LP....
...LP...
....LP..
.....LP.
......LG
......PL

Na drugiej szachownicy król nie może wykonać żadnego ruchu.

Na trzeciej szachownicy król nie może zbić żadnego gońca, ponieważ oba gońce wzajemnie atakują pola, na którym stoją.

Please log in to submit your solution.