Минатата недела, заборавениот професор по ора и танци, Перо, се загубил во еден чуден лавиринт. Лавиринтот претставува правоаголна структура од N*M "соби", соодветно наредени во N редови и M колони. На следната слика е прикажан еден таков лавиринт, со N=4 редови и M=7 колони:

P...... #.##K.. .#.#..# ##..##.

Позицијата на која иницијално се наоѓа Перо е означена со буквата 'P', непристапните соби се означени со знакот '#', додека излезот е означен со 'K' (излезот е всушност лифт кој се наоѓа во собата означена со 'К' и кој ќе го однесе Перо на површината - надвор од лавиринтот). Собите се толку малечки што се поминуваат со еден чекор на професорот.

Уште поголем проблем од фактот што се загубил, е што на професорот му се увртел во глава некој такт на танц, па (мисли дека) мора да прави движења (потези) на следниот начин: Прво треба да направи еден чекор во одредена насока, па два чекори во одредена насока (можеби различна од претходната), па три чекори во одредена насока. Потоа, повторно се движи низ лавиринтот правејќи по еден чекор, па два, па три чекори, и така натаму; се додека не стигне до излезот. Перо треба да пристигне од позицијата означена со 'P' до позицијата означена со 'K', со најмал број на потези - покрај тоа што е заборавен, професорот е и стар, па може да папса пред да стигне до лифтот, ако се матка низ лавиринтот повеќе од неопходното.

Како што веќе споменавме, потезите претставуваат правење 1, 2 или 3 чекори во одредена насока. Како чекор се смета движење од една соба до некоја од нејзините соседни соби (во насока горе, доле, лево или десно). Не е дозволено движење низ непристапни соби, дури и ако тие не се конечната дестинација при одреден потег.

Помогнете му на професорот да стигне на време да го одржи својот час. Напишете програма која, за даден лавиринт, ќе го отпечати најмалиот број на потези со кои може да се стигне од одредена почетна до одредена крајна позиција, почитувајќи го притоа правилото за движење низ лавиринтот (1 чекор, па 2 чекори, па 3, па 1, па 2, па 3, па 1, па 2, ...).

Влез

Во првиот ред се запишани два цели броја: N (3 <= N <= 300) и M (3 <= M <= 300), кои го означуваат бројот на редови и колони од кои е составен лавиринтот. Во секој од следните N редови се наоѓаат по M знаци Sij ('P', 'K', '#' или '.'), кои ја даваат структурата на лавиринтот. Притоа, 'P' ја означува почетната позиција (ќе има само еден ваков знак), 'K' ја означува крајната позиција (ќе има само еден ваков знак), '.' означува соба во која што може да се оди и '#' означува непристапна соба.

Излез

Излезот се состои од еден ред во кој треба да го отпечатите бараниот минимален број на потези. Секогаш ќе постои решение.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
4 7
P......
#.##K..
.#.#..#
##..##.

излез
5

влез
4 7
P......
#.#....
.#.K..#
##..##.

излез
4

влез
4 5
P.#K#
.##.#
.....
.....

излез
5

Објаснување за првиот пример: десно (1 чекор), десно (2 чекори), десно (3 чекори), долу (1 чекор), лево (2 чекори).

Објаснување за вториот пример: десно (1 чекор), десно (2 чекори), долу (3 чекори), горе (1 чекор). Забележете дека, кога Перо направи три чекори надолу, тој помина низ последната соба.