맥주병 화살표 돌리기

Dave는 생일 파티를 준비하고 있습니다. 그는 무알코올 맥주를 병째로 가져와 냉장고에 넣으면서 다음과 같이 쌓았습니다. 먼저 냉장고 맨 아래에 넣을 수 있는 만큼 많은 병을 한 줄로 놓았습니다. 그 위에는 한 병씩 적게 놓되, 새로 놓는 각 병이 아래 줄의 병 두 개 위에 단단히 얹히도록 하여 둘째 줄을 만들었습니다. 이렇게 계속 쌓아 올려 맨 윗줄에는 병 한 개만 놓이도록 했습니다(아래 그림 참고). 모든 병은 뚜껑이 Dave를 향하도록 놓였습니다.

각 뚜껑에는 화살표가 하나씩 그려져 있으며, 화살표는 위, 오른쪽, 아래, 왼쪽 중 한 방향을 가리킵니다.

Dave는 모든 화살표가 위를 향하도록 병들을 돌리려고 합니다. 그런데 병 하나를 돌리면 이웃한 몇몇 병도 함께 돌아간다는 것을 알게 되었습니다. 하나의 단순 회전은 고른 병 하나를 시계 방향으로 90도 돌리는 것입니다. 이때 그 병의 바로 위-왼쪽에 얹힌 병과 위-오른쪽에 얹힌 병이 있다면, 그 병들은 동시에 반시계 방향으로 90도 돌아갑니다. 따라서 하나의 단순 회전은 최대 세 개의 병의 방향을 바꿉니다.

줄은 맨 아래부터 번호를 매기며(가장 아래 줄이 1번), 한 줄 안에서 병은 왼쪽부터 오른쪽으로 1번부터 번호를 매깁니다.

첫째 줄에 정수 N (1 ≤ N ≤ 10)이 주어집니다. N은 맨 아래 줄에 있는 병의 개수입니다.

다음 N개의 줄은 각 줄을 맨 윗줄부터 맨 아랫줄 순서로 나타냅니다. 이 중 i번째 줄에는 정확히 i개의 글자가 왼쪽 병부터 순서대로 주어지며, 각 글자는 그 병의 화살표 방향을 뜻합니다. U는 위, R은 오른쪽, D는 아래, L은 왼쪽입니다.

모든 화살표가 위를 향하게 만들기 위해 필요한 단순 회전의 최소 횟수를 정수 하나로 출력합니다. (이러한 회전 순서는 항상 존재합니다.)