Frogger

Frogger는 SEGA가 1981년에 선보인, 초창기에 크게 유행한 아케이드 게임 중 하나입니다. 목표는 개구리가 자동차에 치이지 않고 여러 차선으로 이루어진 도로를 건너도록 돕는 것입니다.

$n$개의 차선으로 이루어진 도로가 주어집니다. 각 차선은 $m$개의 칸으로 된 한 줄이며, 각 칸은 비어 있거나 자동차 한 대가 놓여 있습니다. 도로의 양쪽 끝에는 연석(curb)이 있어 개구리가 자유롭게 움직일 수 있고, 차선 안에서는 자동차가 없는 칸에만 있을 수 있습니다.

자동차의 진행 방향은 차선마다 번갈아 바뀝니다. 개구리의 출발 연석과 가장 가까운 차선의 자동차는 오른쪽으로, 그다음 차선은 왼쪽으로, 이런 식으로 교대로 이동합니다. 자동차는 차선을 바꾸지 않고 매 턴 정확히 한 칸씩 전진합니다. 교통 흐름을 유지하기 위해, 차선의 한쪽 끝을 벗어나는 자동차는 같은 차선의 반대쪽 끝에서 다시 나타납니다(차선은 순환합니다).

한 턴 동안 모든 자동차는 지정된 방향으로 한 칸씩 이동하고, 개구리는 다음 중 하나를 정확히 한 번 수행합니다: 왼쪽으로 한 칸, 오른쪽으로 한 칸, 위나 아래로 한 칸(두 차선 사이, 또는 연석과 인접한 차선 사이) 이동, 또는 제자리에 머무르기. 자동차와 달리 개구리는 순환할 수 없어, 차선이나 연석의 첫 칸과 마지막 칸 사이를 한 번에 건널 수 없습니다.

개구리와 자동차는 동시에 움직입니다. 따라서 개구리는 이번 턴의 이동이 끝난 뒤 자동차가 없게 될 칸으로만 들어갈 수 있습니다. 이동을 마친 뒤 개구리가 자동차와 같은 칸에 있게 되면 치여서 죽습니다. 이동이 동시에 일어나므로, 같은 차선에서 자신을 향해 다가오는 자동차는 안전하게 뛰어넘을 수 있습니다(개구리와 그 자동차가 서로 칸을 맞바꾸는 셈입니다).

개구리가 한쪽 연석의 출발 칸에서 반대편 연석의 목적지 칸까지 이동하는 데 필요한 최소 턴 수를 구하거나, 주어진 라운드 수 안에 불가능함을 판별하세요.

첫 줄에는 시나리오의 수가 주어집니다.

각 시나리오는 사용할 수 있는 최대 라운드 수를 나타내는 양의 정수 $x$ ($x \le 10^5$)가 적힌 줄로 시작합니다. 다음 줄에는 차선의 수 $n$ ($1 \le n \le 20$)과 각 차선의 길이 $m$ ($1 \le m \le 50$)이 주어집니다.

이어지는 $n + 2$개의 줄에는 각각 $m$개의 문자로 된 문자열이 있습니다.

• X는 자동차,
• O(알파벳 O)는 빈 칸,
• F는 개구리의 출발 칸,
• G는 개구리의 목적지 칸입니다.

이 중 첫 줄은 목적지 연석으로, O들과 정확히 하나의 G로 이루어집니다. 마지막 줄은 출발 연석으로, O들과 정확히 하나의 F로 이루어집니다. 그 사이의 $n$개 줄은 각각 도로의 한 차선을 나타냅니다.

각 시나리오마다 한 줄을 출력합니다.

허용된 라운드 수 안에 개구리가 목적지에 도달할 수 있으면 The minimum number of turns is K.를 정확히 출력합니다. 여기서 K는 최소 턴 수입니다. 그렇지 않으면 The problem has no solution.을 정확히 출력합니다.