Traveling Cellsperson

You have already solved every Project Euler problem in your head, so here is a classic you may have heard of: the traveling salesperson, whose decision version is NP-complete.

This version runs on a rectangular grid. One step moves from the current cell to a cell that shares a side with it, so every cell is connected to the cells above, below, to the left and to the right of it. You may enter the same cell as many times as you like, although most cells are not interesting enough to be worth a second visit.

Exactly one cell is marked S. Start at S, visit every cell of the grid at least once, and come back to S. Find the smallest number of steps such a round trip needs.

The first line contains one integer $T$, the number of test cases. Each test case starts with a line holding two integers $X$ and $Y$, the width and the height of the grid. Then follow $Y$ lines of $X$ characters each, where the character C is a plain cell and the character S is the starting point.

• $0 < T \le 50$
• $0 < X \le 100$
• $0 < Y \le 100$
• In one test case exactly one character is S and every other character is C.

For each test case, print on its own line the minimum number of steps of a round trip that starts at S, visits every cell at least once, and returns to S.

You already know this leads nowhere, so print LOL on a line of its own after the last test case. Print that line once per run, not once per test case.