Olet n \times n ruudukon vasemmassa ylänurkassa ja tavoitteesi on päästä oikeaan alanurkkaan. Saat liikkua ruudukossa oikealle ja alaspäin.

Jokaisessa ruudussa on merkki . (tyhjä) tai * (este). Et voi kulkea ruudun kautta, jos siinä on este.

Mikä on pienin määrä käännöksiä reitillä vasemmasta ylänurkasta oikeaan alanurkkaan?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: ruudukon koko.

Sitten syötteessä on n riviä, joista jokaisella on n merkkiä: ruudukon kuvaus.

Tuloste

Tulosta yksi kokonaisluku: pienin määrä käännöksiä.

Jos mitään reittiä ei ole olemassa, tulosta luku -1.

Rajat

• 1 \le n \le 2500

Esimerkki

Syöte:

4
..*.
..*.
*...
*.*.

Tuloste:

3