Little John likes to play driving games. One of his favorite games involves a horizontal three-lane road divided into cells.
The cells are numbered 0, 1, 2, etc. from left to right, and the lanes are numbered 0, 1, 2 from top to bottom. The car is
initially located in the middle lane in the leftmost cell (lane 1, cell 0). The goal of the game is to reach any lane of the
rightmost cell without hitting any obstacles or leaving the road.
The car moves horizontally one cell at a time. Each time it moves to the next cell, it can either stay in the same lane
or move diagonally to an adjacent lane. More formally, if the car is in lane i, cell j, then after the next move, it can
be in one of the following lanes of cell j+1: i, i-1 (only if i>0), or i+1 (only if i<2).
The road is given as a String road, where the j-th character of the i-th element is the content of lane i,
cell j. '.' represents open road and '#' represents an obstacle. The car hits an obstacle if it ends a move on a '#' character.
Return the fewest number of lane changes necessary to reach the rightmost cell without hitting any obstacles or leaving the
road. If it is impossible to reach the rightmost cell, return -1 instead.