Laiko ribojimas: 0.7s

Atminties ribojimas: 64MB

Duomenų failas: slidininkas.in

Rezultatų failas: slidininkas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Slidininkas

Pagaliau atšilo orai! Deja, ne visiems tas patinka. Vienas iš tokių žmonių yra Vytis, kuris nusprendė pabėgti nuo saulės ir išvykti paatostogauti. Kaip savo atostogų taikinį Vytis išsirinko Šveicariją, kurios kalnuose dar yra sniego ir galima paslidinėti.

Taigi, Vytis nuvyko į savo atostogų vietą ir užkilo ant kalno. Tačiau vos tik tai padarė, jis susidūrė su nauja problema - kaip kuo greičiau apvažiuoti slidinėjimo trasą.

Slidinėjimo trasa M - tai NxN dydžio kvadratas. Vytis pradeda savo kelionę trasos pradžioje - ląstelėje M[1][1], o kelionę nori pabaigti ląstelėje M[N][N]. Trasą sudaro pravažiuojamos vietos pažymėtos tašku '.' bei kliūtys pažymėtos iksu - 'x'. Trasoje taip pat yra vartai (pažymėti žvaigždutėmis - '*'), per kuriuos Vytis privalo pravažiuoti.

Padėkite Vyčiui rasti trumpiausio kelio, pravažiuojant visus vartus, ilgį.

Įvestis

Pirmoje pradinių duomenų eilutėje bus pateiktas skaičius T - testų kiekis (1\\leqT\\leq20). Kiekvienas testas bus pradedamas skaičiumi N - trąsos dydis (1\\leqN\\leq13). Likusiose testo N eilučių bus pateiktas trasos aprašas (vartų skaičius trasoje neviršys 13'kos).

Išvestis

Kiekvienam testui išveskite trumpiausio kelio ilgį arba, jei Vyčiui nepavyks apvažiuoti visų vartų - -1.

Pavyzdys

Pradiniai duomenys Rezultatai 
2
3
..*
.*.
*..
3
...
.x.
x*.
 
8
6