Portal

Chell has to solve a new puzzle from GLaDOS. The room she is in is a matrix with $N$ rows and $M$ columns, and every cell is one of the following:

• a cell with a wall in it, written #
• the cell where Chell starts, written C
• the cell Chell has to reach, written F
• an empty cell, written .

Chell carries a portal gun, a gun that creates portals in walls. In one action she does one of the following.

1. She moves to a neighboring cell up, down, left or right. She cannot move into a cell with a wall in it. This action takes 1 unit of time.
2. She turns up, down, left or right and shoots. The shot flies in that direction and hits the first wall on its way, and the portal appears only on the side of the wall the shot came from. The wall does not have to be next to her. At most two portals exist at the same time. If she creates a portal while two portals already exist, the one created earlier disappears. She cannot create a portal on a side of a wall that already holds a portal. This action takes no time, that is, 0 units of time.
3. If she stands on a cell next to a wall and the side of that wall facing her holds a portal, she can step into that portal and come out on the empty cell that touches the other portal. This is possible only while both portals exist, and it takes 1 unit of time.

A portal stays where it was created until it disappears. Portals do not move when Chell moves. A wall cell has four sides, so two portals can sit on the same wall cell as long as they are on different sides of it.

Find the smallest amount of time Chell needs to solve the puzzle, that is, to reach the cell written F.

The room always has walls along its border, and the letters C and F each appear exactly once.

The first line contains the positive integers $N$ and $M$ ($4 \le N, M \le 500$).

Each of the next $N$ lines contains $M$ characters that describe the room.

Print the smallest amount of time needed to solve the puzzle. If the puzzle cannot be solved, print nemoguce without the quotation marks, which is Croatian for impossible.

The second example can be solved with 8 actions. A cell is written as (row, column).

1. Turn left and shoot. A portal appears on the right side of the wall at (3,1).
2. Shoot down. A portal appears on the upper side of the wall at (6,2).
3. Step into the portal at (3,1) and come out at (5,2).
4. Turn right and shoot. A portal appears on the left side of the wall at (5,7). Two portals already existed, so the one at (3,1) disappears.
5. Step into the portal at (6,2) and come out at (5,6).
6. Shoot up. A portal appears on the lower side of the wall at (1,6), and the portal at (6,2) disappears.
7. Step into the portal at (5,7) and come out at (2,6).
8. Move one cell to the right and finish the puzzle.

Actions 1, 2, 4 and 6 take no time and the other four take 1 unit of time each, so the total time is 4.