First there will be a line containing the number of scenarios you are asked to help the frog in. For each scenario there will first be a line containing a positive integer x <= 10^5 giving the maximum number of rounds that can be used. The next line contains the number of lanes n, 1 <= n <= 20, and the length of each lane m, 1 <= m <=50. Each of the next n + 2 lines will contain a string of m characters. The character X indicates a car, the character O (letter O) indicates a free space, the character F gives the starting position of the frog, and the character G gives the final destination of the frog. The first line indicates the destination curb, consisting of O’s and exactly one G while the last line gives the starting curb consisting of O’s and exactly one F, while the intermediate lines each represent one lane of the motorway.