NinePuzzle

Fox Ciel invented a game called Nine Puzzle. The game is played on a board which is in the form of a regular triangle with side length 4. There are 10 cells on the board, each in the form of a regular triangle with side length 1. The cells are numbered 0 to 9 as shown in the picture below:



Nine of the cells on the board contain a triangular piece. Each piece is painted red, green, blue or yellow. The remaining tenth cell is empty. The goal of the game is to arrange the cells to match a specified goal pattern. To do this, the player can perform the following move any number of times: Choose a piece which is adjacent to an empty cell, and move the piece into that empty cell. Two cells are considered adjacent if the distance between their centers is exactly 1. An example of a valid move is shown in the following picture:



Ciel has painted the triangular pieces to form the starting pattern for the puzzle. She has also chosen the goal pattern. However, she has chosen both these patterns arbitrarily, so it's possible that the puzzle might not be solvable (i.e., it may be impossible to achieve the goal pattern from the given starting pattern using a sequence of valid moves). If this is the case, she would like to repaint the minimum possible number of pieces in the starting pattern to make the puzzle solvable.

You are given two Strings init and goal. The i-th (0-indexed) character of init describes the content of the i-th cell in the starting pattern. The '*' character denotes an empty cell. 'R', 'G', 'B' and 'Y' denote pieces which are colored red, green, blue and yellow, respectively. The goal pattern is described in the String goal in the same format.

Return the minimum number of pieces which must be repainted in the starting pattern to make the puzzle solvable. If the puzzle is already solvable without repainting, return 0.