레일 위의 취미

ICPC(International Connecting Points Company)가 새로운 철도 장난감을 판매하기 시작했습니다. 이 장난감은 장난감 전차 한 대와, 같은 크기의 정사각형 프레임 위에 만들어진 여러 개의 레일 조각으로 구성됩니다. 레일 조각에는 직선(S), 곡선(C), 왼쪽 분기기(L), 오른쪽 분기기(R)의 네 가지 종류가 있습니다. 분기기에는 세 개의 끝이 있습니다: 분기/합류-끝(B/M-끝), 직선-끝(S-끝), 곡선-끝(C-끝)입니다.

분기기는 "직진(through)" 상태이거나 "분기(branching)" 상태입니다. 전차가 B/M-끝으로 들어오면: 분기기가 직진 상태이면 전차는 S-끝으로 나가고 상태가 분기로 바뀌며, 분기 상태이면 전차는 C-끝으로 나가고 상태가 직진으로 바뀝니다. 전차가 S-끝 또는 C-끝으로 들어오면 상태와 관계없이 항상 B/M-끝으로 나가며, 이때 상태는 바뀌지 않습니다.

아이들에게는 $w \times h$ 크기의 직사각형 영역을 채우는 여러 종류의 레일 조각이 주어집니다. 인접한 두 프레임이 맞닿는 변에서 레일 조각들은 자동으로 연결됩니다. 각 레일 조각은 위치는 바꿀 수 없지만, 프레임 중심을 기준으로 90도의 배수만큼 각각 독립적으로 회전시켜 연결 상태를 바꿀 수 있습니다.

아이들은 각 레일 조각을 회전시켜 "유효한(valid)" 배치를 만들어야 합니다. 어떤 배치가 유효하다는 것은, 모든 분기기에 대해 그 세 끝 각각이 (자기 자신을 포함한) 어떤 분기기의 끝과 직접 또는 간접적으로 연결되어 있다는 뜻입니다. 유효하지 않은 배치는 환영받지 못합니다.

유효한 배치에서 전차가 달리면, 결국 같은 경로를 영원히 반복하게 됩니다. 즉 (영역 내에서의 전차의 위치, 진행 방향, 모든 분기기의 상태)라는 삼중항으로 표현되는 동일한 "주행 조건(running condition)"으로 주기적으로 되돌아옵니다.

주기 경로(periodic route)란, 전차가 어떤 주행 조건으로 한 레일 조각에서 출발하여, 처음으로 같은 레일 조각에 같은 주행 조건으로 되돌아올 때까지의 레일 조각들의 나열입니다.

적어도 하나의 분기기를 지나는 주기 경로를 "재미있는 경로(fun route)"라고 부릅니다. 전차가 분기기를 지날 때 내는 덜컹거리는 소리를 아이들이 좋아하기 때문입니다. 전차는 레일 조각의 종류나 진행 방향과 무관하게 각 레일 조각을 지나는 데 동일한 단위 시간을 씁니다. 재미있는 경로의 재미 시간(fun time) $T$는 전차가 그 경로를 한 바퀴 도는 데 걸리는 단위 시간의 수입니다.

아이들은 재미 시간이 긴 배치를 더 좋아합니다. 직사각형 영역에 놓인 레일 조각들이 주어질 때, 이들을 적절히 회전시켜 모든 유효한 배치 가운데 재미 시간이 가장 긴 재미있는 경로를 찾으세요.

예를 들어, $5 \times 2$ 판의 어떤 유효한 배치에는 재미 시간이 24인 재미있는 경로가 있습니다. 모든 분기기가 직진 상태일 때, 전차가 (1, 2)의 B/M-끝에서 (1, 3) 방향으로 출발한다고 합시다. 전차는 (1, 3), (1, 4), (1, 5), (2, 5), (2, 4), (1, 4), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (1, 2)를 지납니다. 이때 (1, 2)에 같은 위치와 방향으로 다시 도달하지만, 분기기 상태는 처음과 다릅니다. 이어서 전차는 (1, 3), (1, 4), (2, 4), (2, 5), (1, 5), (1, 4), (1, 3), (1, 2), (2, 2), (2, 1), (1, 1), (1, 2)를 지납니다. 이제 (1, 2)에 처음과 같은 분기기 상태로 다시 도달합니다. 지난 레일 조각의 수를 세면 전차는 24 단위 시간을 달렸으므로, 재미 시간은 24입니다.

같은 레일 조각들로 만들 수 있는 유효한 배치는 여러 개일 수 있습니다. 어떤 유효한 배치에는 재미 시간이 120인 재미있는 경로가 있을 수 있고, 그 배치에서 네 개의 레일 조각의 회전만 바꾼 또 다른 배치에는 재미 시간이 148인 재미있는 경로가 있을 수 있습니다.

하나의 유효한 배치에 여러 개의 재미있는 경로가 있을 수도 있습니다. 예를 들어 어떤 배치에는 두 개의 재미있는 경로가 있는데, 하나는 (1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (3, 2), (2, 2), (1, 2) 조각들을 지나며 $T = 8$이고, 다른 하나는 나머지 모든 조각을 지나며 $T = 18$입니다. 같은 판의 또 다른 배치에는 $T = 12$와 $T = 20$인 두 재미있는 경로가 있으며, 그 판의 어떤 유효한 배치에도 재미 시간이 20보다 긴 재미있는 경로는 없으므로 가장 긴 재미 시간은 20입니다.

유효한 배치에는 어떤 분기기도 지나지 않는 단순 순환 경로가 포함될 수 있는데, 이는 재미있는 경로가 아닙니다. 예컨대 어떤 배치에는 재미 시간이 12와 14인 두 재미있는 경로와, 한 바퀴 도는 데 20이 걸리는 단순 순환 경로가 함께 있을 수 있습니다. 20이 더 크더라도 가장 긴 재미 시간은 여전히 14입니다.

입력은 여러 개의 데이터셋으로 이루어지며, 공백으로 구분된 두 개의 0으로만 이루어진 줄로 끝납니다. 각 데이터셋의 형식은 다음과 같습니다:

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

$w$는 한 행에 있는 레일 조각의 수, $h$는 한 열에 있는 레일 조각의 수입니다. 각 $a_{ij}$ ($1 \le i \le h$, $1 \le j \le w$)는 대문자 S, C, L, R 중 하나로, 위치 $(i, j)$에 있는 레일 조각의 종류(각각 직선, 곡선, 왼쪽 분기기, 오른쪽 분기기)를 나타냅니다. 한 줄의 항목들은 공백으로 구분됩니다.

$2 \le w \le 6$, $2 \le h \le 6$이고, 왼쪽 분기기와 오른쪽 분기기의 개수 합이 2 이상 6 이하라고 가정해도 됩니다.

각 데이터셋에 대해, 주어진 레일 조각들로 만들 수 있는 모든 유효한 배치의 모든 재미있는 경로 가운데 가장 긴 재미 시간을 정수 하나로 한 줄에 출력하세요. 유효한 배치가 하나도 없으면 0을 출력하세요.