9-퍼즐

영선이의 아이디는 nein이다. 숫자 9를 좋아하기 때문이다. 그런데 왜 nein일까? 아이디를 만들 당시 영선이는 9가 영어로 nein인 줄 알았다.

9를 좋아하는 영선이는 9-퍼즐이라는 게임을 만들었다. 이 게임은 변의 길이가 4인 정삼각형 보드 위에서 진행된다. 보드는 10개의 칸으로 이루어져 있고, 각 칸은 변의 길이가 1인 정삼각형이다. 칸에는 아래 그림처럼 0번부터 9번까지 번호가 매겨져 있다.

10개의 칸 중 9개에는 삼각형 조각이 하나씩 들어 있다. 각 조각의 색은 빨간색, 초록색, 파란색, 노란색 중 하나이다. 나머지 한 칸은 비어 있다. 게임의 목표는 특정한 패턴을 만드는 것이고, 이를 위해 영선이는 조각을 인접한 빈 칸으로 옮긴다. 두 칸의 중심 사이 거리가 1이면 두 칸이 인접해 있다고 한다. 아래 그림은 올바른 이동의 한 예이다.

현재 9-퍼즐의 조각 상태와 영선이가 목표로 하는 조각 상태가 입력으로 주어진다. 두 상태는 무작위로 골랐기 때문에 게임을 풀 수 없는 경우도 있다. 두 상태가 주어졌을 때, 게임을 풀 수 있게 만들기 위해 다시 색칠해야 하는 조각의 최소 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 현재 상태, 둘째 줄에 목표 상태가 주어진다. 각 상태는 길이가 10인 문자열이며, $i$번째 글자는 $i$번 칸의 색을 나타낸다 ($0 \le i \le 9$). R은 빨간색, G는 초록색, B는 파란색, Y는 노란색, *는 빈 칸이다. 각 상태에서 빈 칸은 항상 정확히 한 개이다.

첫째 줄에 퍼즐을 풀 수 있게 만들기 위해 다시 색칠해야 하는 조각의 최소 개수를 출력한다.

첫 번째 예제는 다음과 같이 풀 수 있다.