Finally, Wodex met Zero. But Zero wore a mask, so Wodex could not see the face.
There was a steep cliff between them. So, Wodex could not go to the other side.
Zero said," I have two games to share with you, if you win, you can go to in front of me, but which game do you like?"
Wodex," I'd like second one."
Zero," OK! Later, there will be a map sized of M * M on the top of the steep cliff, and you can only begin at (0, 0), and the entrance to go to my side is at (M - 1, M - 1).
There are only two possible things in the map, blank space or the wall. Blank space means you can go, but te wall means you can not go. When the game is beginning, I will choose a lattice (a, b) named the black hole. When you go one step, the black hole will spread to the adjacent lattice. When a lattice with the black hole, it means the black hole will never disappear on this lattice. When you begin the game, you will be at (0, 0), and the black hole will be at (a, b), so can you successfully arrive at (M - 1, M - 1)? If you touch the black hole, you will die.
The first black hole will be possible at the wall, it is the same as at the blank space. But after, the black hole can not spread to the wall, only spread to the blank space.
If Wodex can arrive at (M - 1, M - 1), print the number of steps. Otherwise print 'Wodex lost the game!'.