Król Pasibrzuch Brzuchaty

Król Pasibrzuch Brzuchaty, jak jego przydomek wskazuje, lubi sobie smacznie pojeść. Pewnego dnia wstał rano i ku swojemu zdumieniu odkrył, że nie ma przy nim jego sługi, który zawsze podawał mu śniadanie do łóżka. Dlatego też król musi sam pofatygować się do stołu z jedzeniem.

Komnata króla ma postać prostokąta o n rzędach i m kolumnach. W niektórych polach komnaty są meble, przez które król przejść nie potrafi, je w wejściu oznaczamy symbolem X. Król jest oznaczony literką K, stół z jedzeniem zaś literką S. Kropki (.) oznaczają pola, po których król może się spokojnie poruszać.

Król rusza się jak król w szachach - na jedno z 8 sąsiednich pól. Dodatkowo jednak, król jest dość gruby. W związku z tym między kolejnymi ruchami (krokami?) może skręcić o co najwyżej 45 stopni. To znaczy, jeśli właśnie przeszedł z pola o współrzędnych (4, 5) do pola (3, 4) to w następnym ruchu może się ruszyć tylko na pola (2, 3), (3, 3) i (2, 4). Jeśli zaś z pola (4, 5) poszedł na pole (4, 6), to w następnym ruchu może się ruszyć na pola (4, 7), (5, 7) i (3, 7).

Król jest bardzo głodny. Wyznacz, ile minimalnie kroków musi zrobić, aby dostać się do stołu z jedzeniem.

Wejście

Pierwsza linia wejścia zawiera dwie liczby n i m, 1 <= n, m <= 300. Kolejne n wierszy zawiera po m znaków, opisujących komnatę króla. Znak w wierszu i+1 na pozycji j oznacza, co jest w komnacie na współrzędnych (i, j). Jeśli pole jest puste, jest to znak kropki (.). Jeśli jest tam mebel, to w wejściu jest X. Król oznaczony jest literką K, stół - literką S. Jest dokładnie jedna literka S i dokładnie jedna literka K.

Wyjście

Wypisz 1 liczbę całkowitą, oznaczającą minimalną liczbę kroków, jakie musi wykonać król, by dojść do stołu z jedzeniem. Jeśli jest to niemożliwe, i król umrze z głodu, wypisz słowo NIE.

Przykład

Dla wejścia

7 8
...X...X
.S.X.K..
.XX.X...
X...XX..
...XX...
.X....XX
..X.....

prawidłową odpowiedzią jest:

12