URI Online Judge | 2928

Crossing Lakes

Por Felipe C. Ochial, URI BR Brazil

Timelimit: 1

The north pole has been facing a logistics problem due to global warming. This is due to the fact that the factory and the toy store are on opposite sides of a lake that used to be frozen all year round. However, with the increase in temperature in the last years the ice that covers the lake has become less and less thick. To get around the problem Balladug, a very clever Elvish gnome, has created a radar that can map the thickness of the ice. So Balladug delivered the map to the elven gnomes in charge of transport. These gnomes can jump up to a maximum distance of 2 meters. With the map in hand, the gnomes wonder if it is possible to cross the ice lake with their jumps and if possible they would like to know how many jumps they have to give for such.

Input

The input consists of an integer N (0 <N<101) representing the number of rows in the map. The next N lines contain up to 10 characters where the character "-" represents a region of firm ice and the character "." represents a region of thin ice that will break if it is stepped on. Each line is one meter wide on the map. Consider that the gnomes start in the upper left corner and must cross the entire lake until they reach any position on the opposite shore that lies behind the last line of the map.A line will always consist entirely of the same character.

Output

The output consists of an integer indicating the number of jumps to go through the lake or the "N" character if it is impossible to cross the lake. Do not forget to leave a blank line after the answer.

Input Sample Output Sample

10

------

......

------

------

------

......

......

------

------

------

2

7

-----

.....

.....

.....

-----

-----

.....

N

2

---------

.........

1