Hobby on Rails

ICPC (International Connecting Points Company) starts selling a new railway toy. It consists of a toy tramcar and many rail units built on square frames of the same size. There are four types of rail unit: straight (S), curve (C), left-switch (L) and right-switch (R). A switch has three ends: the branch/merge-end (B/M-end), the straight-end (S-end) and the curve-end (C-end).

A switch is in either the "through" state or the "branching" state. When the tramcar arrives from the B/M-end: if the switch is in the through state it leaves from the S-end and the state becomes branching; if the switch is in the branching state it leaves from the C-end and the state becomes through. When the tramcar arrives from the S-end or the C-end, it always leaves from the B/M-end and the state does not change.

Kids are given rail units of various types that fill a rectangular area of $w \times h$ frames. Rail units meeting at the shared edge of two adjacent frames are automatically connected. Each rail unit may be independently rotated about the center of its frame by a multiple of 90 degrees to change the connections, but its position cannot be changed.

Kids should make "valid" layouts by rotating each rail unit. A layout is valid when, for every switch, each of its three ends is directly or indirectly connected to an end of some switch (possibly the same switch). Invalid layouts are frowned upon.

When the tramcar runs in a valid layout, it eventually begins to repeat the same route forever: it periodically returns to the same running condition, which is the triple of (the tramcar's position in the area, its direction, and the states of all switches).

A periodic route is a sequence of rail units on which the tramcar starts from a rail unit with a running condition and returns to the same rail unit with the same running condition for the first time.

A periodic route that passes through at least one switch is called a "fun route", because kids like the rattling sound the tramcar makes as it passes a switch. The tramcar takes the same unit of time to pass through each rail unit, independent of the unit's type or the tramcar's direction. The fun time $T$ of a fun route is the number of time units the tramcar takes to go once around the route.

Kids enjoy layouts with a longer fun time more. Given the rail units placed on a rectangular area, rotate them appropriately and find the fun route with the longest fun time among all valid layouts.

For example, one valid layout of a $5 \times 2$ board has a fun route with fun time 24. Let the tramcar start from the B/M-end at (1, 2) heading toward (1, 3) with every switch in the through state. It passes (1, 3), (1, 4), (1, 5), (2, 5), (2, 4), (1, 4), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (1, 2). Here it reaches (1, 2) again with the same position and direction but with different switch states. It then passes (1, 3), (1, 4), (2, 4), (2, 5), (1, 5), (1, 4), (1, 3), (1, 2), (2, 2), (2, 1), (1, 1), (1, 2). Now it reaches (1, 2) again with the same switch states as at the start. Counting the rail units visited, the tramcar ran 24 units of time, so the fun time is 24.

There may be many valid layouts for the same rail units. One valid layout may contain a fun route with fun time 120, and another obtained from it by changing the rotation of four rail units may contain a fun route with fun time 148.

A single valid layout may contain several fun routes. For example, one layout contains two fun routes: one over the units (1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (3, 2), (2, 2), (1, 2) with $T = 8$, and one over all the remaining units with $T = 18$. Another layout of the same board has two fun routes with $T = 12$ and $T = 20$; no valid layout of that board has a fun route with fun time longer than 20, so the longest fun time is 20.

Note that a valid layout may also contain simple cyclic routes that do not pass through any switch; these are not fun routes. For instance, a layout may have two fun routes with fun times 12 and 14 together with a simple cyclic route whose going-around time is 20. Even though 20 is larger, the longest fun time is still 14.

The input consists of several datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format:

w h
a11 a12 ... a1w
...
ah1 ah2 ... ahw

$w$ is the number of rail units in a row and $h$ is the number of rail units in a column. Each $a_{ij}$ ($1 \le i \le h$, $1 \le j \le w$) is one of the uppercase letters S, C, L, R, giving the type of the rail unit at position $(i, j)$: straight, curve, left-switch, and right-switch respectively. Items on a line are separated by a space.

You may assume $2 \le w \le 6$, $2 \le h \le 6$, and that the number of left-switches plus right-switches is at least 2 and at most 6.

For each dataset, print on its own line a single integer: the longest fun time over all fun routes in all valid layouts obtainable from the given rail units. If there is no valid layout, print 0.