Šeštadieninė informatikos olimpiadininkų mokykla

Daugelis gerai žino žaidimą 15: 4x4 dydžio lentelėje atsitiktine tvarka surašyti skaičiai nuo 1 iki 15, o vienas langelis paliktas tuščias; į šį tuščią langelį galima "perstumti" skaičių iš gretimo langelio (tuomet šis tampa tuščias). Žaidimo tikslas - sustumdyti skaičius taip, jog jie lentelėje būtų surašyti iš eilės, o tuščias liktų paskutinis langelis (taip, kaip parodyta paveiksle).

Žaidimas 8 - tai sumažintas žaidimo 15 variantas (žaidžiama 3x3 dydžio lentelėje). Parašykite programą, kuri rastų, kiek mažiausiai ėjimų pakanka duotam žaidimui laimėti, arba nustatytų, kad laimėti neįmanoma.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas žaidimų skaičius T (). Toliau seka T žaidimo aprašymų. Kiekvieną aprašymą sudaro trys eilutės, kuriose įrašyta po tris skaičius nuo 0 iki 8 (skaičiai viename žaidimo aprašyme nesikartoja - tai pradinis skaičių išdėstymas lentelėje). Skaičius 0 žymi tuščią langelį. Prieš kiekvieną žaidimo aprašymą įrašyta tuščia eilutė.

Rezultatai

Rezultatų failą turi sudaryti T eilučių. Kiekvienam žaidimo aprašymui, iš eilės, turi būti įrašytas mažiausias ėjimų skaičius, reikalingas tam žaidimui laimėti. Jei žaidimo laimėti neįmanoma, turi būti įrašytas -1.

Pavyzdžiai

3


1 2 3
5 7 6
0 4 8


1 3 5
4 2 6
0 7 8


3 4 5
1 8 2
0 7 6

6
8
12