Surely everyone is familiar children's game "\textbf{15}". In this problem, we consider a simple game - "\textbf{8}". The playing field in this game is a square of \textbf{3}x\textbf{3} cells. There are 8 square pieces, numbered with numbers from \textbf{1} to \textbf{8}. These chips are randomly placed in the cells of the field. One cell remains free. In one move, you can move on the free cell field any adjacent chips, ie a chip, standing on the right or left, or top or bottom of the free cells. Goal of the game - moving the pieces on the playing field as described above, to place all the chips in the correct order: \textbf{123} \textbf{456} \textbf{780} number \textbf{0} denotes the empty box. You need to a given initial position of chips to determine the minimum number of moves for which you can arrange the pieces in the correct order. number 0 denotes the empty box. You need to a given initial position of chips to determine the minimum number of moves for which you can arrange the pieces in the correct order. \InputFile The input file contains the starting position in the game. The position is defined by three rows, each of which recorded three digits without spaces. To set the position using numbers from \textbf{0} to \textbf{8}. Each digit occurs exactly once. \OutputFile The only line in the output file should contain the minimum number of moves for which you can arrange the pieces in the correct order. If the input data such that the chips can arrange, you must withdraw \textbf{-1} (minus one). The output should end with a newline. The input file contains the starting position in the game. The position is defined by three rows, each of which recorded three digits without spaces. To set the position using numbers from 0 to 8. Each digit occurs exactly once.