이세계 게임

트럭 운전사 택희는 오랜 공로를 인정받아 이세계로 소환되었다. 그 세계에는 천사 종족 Portableangel과 악마 종족 Legnaelbatrop이 살고 있다. 택희는 뛰어난 알고리즘 지식으로 곧 두 종족을 모두 다스리는 왕이 되었다.

지루해진 택희는 주민 16명을 종족과 관계없이 골라 4×4 격자에 세운 뒤, 각 칸에 서야 할 종족을 새로 지정한다. 주민들은 택희가 원하는 배치가 되도록 서로 자리를 바꾸어야 한다. 한 번의 자리 바꿈에서는 상하좌우로 인접한 두 주민만 서로 바꿀 수 있으며, 같은 주민이 여러 번 자리를 바꿔도 된다.

현재 배치와 원하는 배치가 주어질 때, 원하는 배치를 만들기 위한 최소 자리 바꿈 횟수를 구하라.

'P' 또는 'L'로만 이루어진 길이 4의 문자열 4개가 공백 없이 주어진다. 이는 현재 배치를 나타내며, 'P'는 Portableangel, 'L'은 Legnaelbatrop을 뜻한다.

그 뒤 빈 줄이 0개 이상 주어진 뒤, 같은 형식으로 원하는 배치가 주어진다. 불가능한 배치는 주어지지 않는다.

원하는 배치를 만들기 위해 필요한 최소 자리 바꿈 횟수를 출력한다.