Masala #0524

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

1. O'yin 2xN kenglikdagi yo'lakchada bo'lib o'tadi.
2. O'yin boshida poyga mashinasi 1-qatorning bo'sh katakchasidan joy oladi.
3. 2xN yo'lakning har bir qatorining istalgan joyda albatta bitta to'siq bo'ladi.
4. Mashina oldingi qatorning istalgan to'siqsiz katakchasiga bitta urinishda yura oladi.

Siz mashina "Finish"ga yetib borishi uchun eng kamida nechta urunish amalga oshirishi kerak ekanligini topishingiz kerak.

Birinchi satrda o'yin oynaladigan yo'lakdagi qatorlar soni N. Keyingi N ta satrda esa yo'lakdagi gar bir qatorning holati. Bu yerda '*' mashina yurishi mumkin bo'lgan katak, '#' esa shu qatordagi to'siqni bildiradi. 

Minimal urinishlar soni.