With each output depending only on a pair of integers ~(R, C)~, it's safe to guess that some sort of patterns can be found for small values of ~(R, C)~ which can extend to arbitrarily large values. It may be tempting to try solving various small cases by hand to look for such patterns, and it's simple to do so for some (such as when one dimension is equal to ~1~ or ~2~), but overall it proves far too difficult to do so for others. So, our best bet will be to write some code which can (inefficiently) find answers for small grids, and then look for patterns in its results.

The most standard approach is with breadth-first search, in which the state includes information about which subset of cells have been visited, what cell the lawnmower is currently in, what direction it's facing in, and whether or not it turned just before its last move. This gives us ~2^{R \times C} \times R \times C \times 4 \times 2~ states, with up to ~3~ transitions from each state.

Many states are unreachable, so we'll want to hash states to track their reachability rather than maintaining a boolean array of that size. This sort of BFS ends up running in a reasonable amount of time (under a minute) for any grid such that ~R \times C~ is at most ~40~ or so, which will suffice for our purposes.

Now, let's talk about the patterns which surface. For convenience, let ~A = \min(R, C)~ and ~B = \max(R, C)~, and let's talk in terms of the minimum number of "wasted" moves ~W~ (such that the answer is equal to ~RC-1+W~). If we run our BFS for all possible grids with ~1 \le R, C \le 6~, we can come up with the following observations:

• When ~A = 1~, ~W = 0~.
• When ~A = 2~, it's impossible.
• When ~A = 3~ and ~B = 3~, it's impossible.
• When ~A = 3~ and ~B \ge 4~, there's no clear pattern?
• When ~A = 4~, ~W = 4~. If we examine the optimal lawnmower path for a ~4 \times 4~ grid, it's relatively clear that it can be easily stretched out to arbitrarily large values of ~B~, and that larger values of ~B~ can't help improve it.
• When ~A \ge 5~, ~W = 2~. If we examine the optimal lawnmower path for a ~5 \times 5~ grid, it's relatively clear that it can be extended to larger grid sizes without wasting any additional moves (by either stretching it out along one dimension or repeatedly wrapping around the outside to increase both dimensions), and that larger grid sizes can't help improve it.

The only problematic case is when ~A = 3~ and ~B \ge 4~, which requires further investigation. It's once again safe to guess that a pattern will emerge for relatively small values of ~B~ which can extend to arbitrarily large values. To search for the pattern, we can try running our BFS again for as many ~3 \times B~ grids as possible, which works reasonably up to around ~B = 15~.

Unfortunately, this is insufficient for the pattern to become completely obvious, but it is enough to guess it correctly. The ~W~ values for ~B = 4 \dots 11~ are unpredictable (~[4, 4, 6, 8, 10, 10, 10, 12]~), but starting at ~B = 12~ they finally start to repeat regularly (~[14, 14, 16, 16, 18, 18, 20, 20, \dots]~). To gain full confidence, it's also possible to write a more specialized brute force algorithm for ~3 \times B~ grids (or even use dynamic programming) to compute all ~W~ values up to much larger values of ~B~, though that's less viable in the limited contest time.

With that, all possible cases have been covered! For ~A = 3~ and ~4 \le B \le 11~, we can either run our BFS or hardcode the values listed above, and for all other cases we have closed-form formulae for the answers.