Egy régi templomban Miloš különös, misztikus sakktáblára akadt. Ennek a táblának \(h\) sora, és \(w\) oszlopa van. Egyes mezőit valamilyen mágia segítségével zárolták. Teljesen megigézte ez a tábla, és elkezdett vele egy különös játékot játszani.

A táblán mindig csak egy figura lehet, amelyet Miloš másikra cserélhet. Kezdetben ez a király, a bal felső \((1,1)\) mezőn. A figurák ugyanúgy mozognak, mint a hagyományos sakk esetében azzal, hogy a zárolt mezőkre nem léphetnek. Minden figura elmozdításához Milošnak 1 másodpercre van szüksége. Célja az, hogy mielőbb elhelyezzen egy figurát a jobb alsó, \((h,w)\) mezőn.

Egy tetszőleges pillanatban Miloš a táblán lévő figurát lecserélheti az adott mezőn egy másikra. A csereművelethez azonban bizonyos időre van szüksége. Ez az idő attól függ, hogy melyik figurát kezdi el használni.

Király : Milošnak 1 másodpercre van szüksége, hogy bármelyik figurát királyra cserélje.
A király egy elmozdítás hatására a 8 szomszédos mező közül bármelyikre léphet, ha az nem zárolt.




Futó: Milošnak 2 másodpercre van szüksége, hogy bármelyik figurát futóra cserélje.
A futó mindaddig haladhat átlósan, egyetlen elmozdítás hatására, amíg zárolt mező nem állja útját.




Bástya: Milošnak 3 másodpercre van szüksége, hogy bármelyik figurát bástyára cserélje.
A bástya egyetlen elmozdítás hatására haladhat balra, jobbra, felfelé vagy lefelé tetszőleges számú mezőn keresztül, amíg zárolt mező nem állja útját.



Huszár: Milošnak 4 másodpercre van szüksége, hogy bármelyik figurát huszárra cserélje.
A huszár egyetlen elmozdítás hatására 2 lépést tehet balra, jobbra, felfelé vagy lefelé, és egy lépést merőlegesen az előző irányhoz viszonyítva. Zárolt mezőkön is áthaladhat.



Vezér: Milošnak 5 másodpercre van szüksége, hogy bármelyik figurát vezérre cserélje.
A vezér egyetlen elmozdítás hatására haladhat balra, jobbra, felfelé vagy lefelé, vagy akár átlósan is mindaddig, amíg zárolt mező útját nem állja.


Segítsetek Milošnak, és mondjátok meg neki, hogy mennyi az a legrövidebb idő, amely alatt befejezheti a játékot, vagy közöljétek vele, ha ez nem lehetséges.

Bemenet

A szabványos bemenet első sorában két természetes szám \(h\) és \(w\) található, amelyek sorrendben a tábla magasságát és szélességét adják meg. A következő \(h\) sorban egy - egy \(w\) hosszúságú sorozat található. Ezekben a sorozatokban . és # karakterek vannak, ahol a . szabad mezőt, а # pedig zárolt mezőt definiál.

Kimenet

A kimeneten kiíratni a \(t\) egész számot, amely a legrövidebb időt jelenti másodpercekben, amely szükséges, hogy Miloš figurát helyezzen el a \((h,w)\) mezőn, illetve \(-1\)-t, ha az nem lehetséges.

1. példa

Bemenet

3 3
...
.#.
...

Kimenet

3

2. példa

Bemenet

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

Kimenet

6

3. példa

Bemenet

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

Kimenet

8

Magyarázat

1. példa:

2. példa:

3. példa:

Korlátozások

• \(1 \leq h,w \leq 500\)

A tesztpéldák 5 független csoportba oszthatók:

• Tesztpéldák, melyek \(10\) pontot érnek: \(h,w \leq 5\).

• Tesztpéldák, melyek \(10\) pontot érnek: \(h,w \leq 200\), és ha létezik megoldás, létezik optimális megoldás is, amely nem igényel figuracserét.

• Tesztpéldák, melyek \(40\) pontot érnek: \(h,w \leq 200\).

• Tesztpéldák, melyek \(10\) pontot érnek: ha létezik megoldás, létezik optimális megoldás is, amely nem igényel figuracserét.

• Tesztpéldák, melyek \(30\) pontot érnek: külön korlátozások nélkül.