Tokom istraživanja starog hrama, Miloš je našao mističnu šahovsku tablu koja ima ~h~ redova i ~w~ kolona na kojoj su neka od polja blokirana uz pomoć magije. On je postao opsednut ovom tablom i krenuo da igra veoma neobičnu igru na njoj.

Na tabli se uvek nalazi tačno jedna figura koju Miloš u toku igre može da zamenjuje drugim figurama. Na početku igre to je kralj koji se nalazi na gornjem levom polju, ~(1,1)~. Figure se pomeraju po uobičajenim pravilima šaha, međutim nije moguće staviti ih na blokirana polja. Za svako pomeranje figure Milošu treba 1 sekund. Njegov cilj je da što pre stavi neku figuru na donje desno polje, ~(h,w)~.

U proizvoljnom momentu Miloš može da zameni trenutnu figuru nekom drugom figurom na istoj toj poziciji. Međutim, on ne može ovo da uradi trenutno, nego mu za to treba određeno vreme, u zavisnosti od toga koju novu figuru počinje da koristi.

Kralj : Milošu treba 1 sekund da zameni bilo koju figuru kraljem.
Kralj se u jednom potezu može pomeriti na jedno od 8 susednih polja ako to polje nije blokirano.




Lovac: Milošu treba 2 sekunde da zameni bilo koju figuru lovcem.
Lovac se u jednom potezu može pomeriti dijagonalno proizvoljan broj polja, sve dok ni jedno od polja na njegovom putu nije blokirano.



Top: Milošu treba 3 sekunde da zameni bilo koju figuru topom.
Top se u jednom potezu može pomeriti levo, desno, gore ili dole proizvoljan broj polja, sve dok ni jedno od polja na njegovom putu nije blokirano.



Konj: Milošu treba 4 sekunde da zameni bilo koju figuru konjem.
Konj se u jednom potezu može pomeriti 2 polja u proizvoljnom od četiri smera (gore, dole, levo, desno) i 1 polje u jednom od dva smera ortogonalna na prethodni smer. Nije bitno da li su polja preko kojih konj usput prelazi blokirana ili ne.


Kraljica: Milošu treba 5 sekundi da zameni bilo koju figuru kraljicom.
Kraljica, u jednom potezu, može da se pomeri levo, desno, gore, dole ili dijagonalno proizvoljan broj polja, sve dok ni jedno od polja na njenom putu nije blokirano.


Pomozite Milošu i recite mu za koliko najmanje sekundi može da završi ovu igru, ili mu saopštite da to nije moguće.

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se dva prirodna broja ~h~ i ~w~, koji obeležavaju redom visinu i širinu table. U narednih ~h~ redova se nalazi niz dužine ~w~ koji se sastoji samo od karaktera . i #, gde . označava da je polje slobodno, a # da je polje blokirano.

Opis izlaza

Na izlaz ispisati ceo broj ~t~, najmanji broj sekundi da Miloš postavi figuru na polje ~(h,w)~, odnosno ~-1~ ako to nije moguće.

Primer 1

Ulaz

3 3
...
.#.
...

Izlaz

3

Primer 2

Ulaz

3 5
.####
##.##
####.

Izlaz

6

Primer 3

Ulaz

10 10
...#.###..
.....#####
...##..#.#
#....#....
.#.......#
##..#.....
......#...
..##..#.#.
..#..#..#.
..#..##...

Izlaz

8

Objašnjenje primera

Primer 1:

Primer 2:

Primer 3:

Ograničenja

• ~1 \leq h,w \leq 500~

Test primeri su podeljeni u 5 disjunktnih grupa:

• U test primerima vrednim ~10~ poena: ~h,w \leq 5~.
• U test primerima vrednim ~10~ poena: ~h,w \leq 200~ i ako postoji rešenje, postoji i optimalno rešenje koje ne zahteva zamenu figura.
• U test primerima vrednim ~40~ poena: ~h,w \leq 200~.
• U test primerima vrednim ~10~ poena: Ako postoji rešenje, postoji i optimalno rešenje koje ne zahteva zamenu figura.
• U test primerima vrednim ~30~ poena: Bez dodatnih ograničenja.