Masala #0533

Eski Nokia telefonlaridagi Racing o'yini yodingizdami? O'yin shartlari quyidagicha.

1. O'yin NxN kenglikdagi yo'lakchada bo'lib o'tadi;
2. O'yinda poyga mashinasi (1, 1) katakchadan yurishni boshlaydi.
3. Mashina chap, o'ng va pastga harakatlana oladi.
4. Finish (N, N) katakcha hisoblanadi.

Siz mashina "Finish"ga yetib borishi uchun eng kamida necha marotaba harakatni amalga oshirishi kerak ekanligini topishingiz kerak. 

Kiruvchi ma'lumotlarning birinchi satrida o'yin o'ynaladigan yo'lakning o'lchami \(N\)\((2\leq N\leq 50)\). Keyingi \(N\) ta satrda \(N\) tadan belgi, bu belgilar ikkita belgini o'z ichiga oladi, * bu yurish mumkun bo'lgan katakcha, # bu esa to'siq mavjud bo'lgan katakchani ifodalaydi.

Chiqish faylida o'yinda mashina Finishga yetib borishi uchun minimal harakatni chop eting, agar yetib borishning imkoni bo'lmasa -1 ni chop eting.