Frogger

Frogger, introduced by SEGA in 1981, was one of the first hugely popular arcade games. The goal is to help a frog cross a multi-lane motorway without being run over by a car.

You are given an $n$-lane motorway. Each lane is a row of $m$ cells, and every cell is either empty or occupied by a car. On each side of the motorway there is a curb where the frog can move freely; inside the traffic lanes the frog may only stand on cells that are not occupied by a car.

The travel direction alternates from lane to lane. The cars in the lane closest to the frog's starting curb move to the right, the cars in the next lane move to the left, and so on. Cars never change lanes and advance exactly one cell per turn. To keep traffic flowing, a car that would leave one end of its lane reappears at the opposite end of the same lane (the lanes wrap around).

In one turn every car moves one cell in its assigned direction, and the frog does exactly one of the following: move one cell left, move one cell right, move one cell up or down (between two lanes, or between a curb and the neighbouring lane), or stay where it is. Unlike the cars, the frog cannot wrap around; it can never step directly between the first and last cell of a lane or a curb.

The frog and the cars move simultaneously, so the frog may step onto a cell only if that cell will be free of cars after this turn's movement. If, after moving, the frog occupies the same cell as a car, it is run over and dies. Because the moves happen at the same time, the frog may safely leap over a car that is approaching it in its own lane (the frog and that car simply swap cells).

Compute the minimum number of turns the frog needs to travel from its starting cell on one curb to its destination cell on the curb on the other side of the road, or report that this is impossible within the given number of rounds.

The first line contains the number of scenarios.

Each scenario begins with a line containing a positive integer $x$ ($x \le 10^5$), the maximum number of rounds that may be used. The next line contains two integers: the number of lanes $n$ ($1 \le n \le 20$) and the length of each lane $m$ ($1 \le m \le 50$).

The following $n + 2$ lines each contain a string of $m$ characters:

• X is a car,
• O (the letter O) is a free cell,
• F is the frog's starting cell,
• G is the frog's destination cell.

The first of these lines is the destination curb: it consists of Os and exactly one G. The last line is the starting curb: it consists of Os and exactly one F. Each of the $n$ lines in between is one lane of the motorway.

For each scenario, print one line.

If the frog can reach its destination within the allowed number of rounds, print exactly The minimum number of turns is K., where K is that minimum number of turns. Otherwise, print exactly The problem has no solution.