#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 3
#define TRUE 1
#define FALSE 0

int x[4]={0,-1,0,1};
int y[4]={1,0,-1,0};
int l;
int puzzle[N][N];

void swap(int *,int *);
int abc();
int dfs(int,int,int,int);
void Solved(int,int);

int main()
{
  int i,j,sx,sy;
   
   for(i=0;i<N;i++){
     for(j=0;j<N;j++){
       scanf("%d",&puzzle[i][j]);
        if(puzzle[i][j]==0){
            sy=i;sx=j;
        }
     }
   }
   Solved(sy,sx);
   return 0;
}


void swap(int *x,int *y)
{
  int tmp;
  tmp=*x;
  *x=*y;
  *y=tmp;
}


int abc()
{
  int i,j,s=0,r;
  
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
        
        if(puzzle[i][j]==0)continue;
        
        r=puzzle[i][j]-1;
        s+=abs(r/N-i)+abs(r%N-j);
    }
  }
  return s;
}


int dfs(int d,int p,int sy,int sx)
{
  int i,m;
  int tx,ty;

  m=abc();
  
  if(m==0)return TRUE;
  if(d+m>l)return FALSE;
  
  for(i=0;i<4;i++){
    if(abs(i-p)==2)continue;
    
    tx=sx+x[i],ty=sy+y[i];
    
    if(tx<0||ty<0||tx>=N||ty>=N)continue;
    
    swap(&puzzle[ty][tx],&puzzle[sy][sx]);
    
    if(dfs(d+1,i,ty,tx))return TRUE;
    
    swap(&puzzle[ty][tx],&puzzle[sy][sx]);
  }
    return FALSE;
}


void Solved(int sy,int sx)
{
  for(l=0;;l++){
    if(dfs(0,99,sy,sx)){
      printf("%d\n",l);
      return ;
    }
  }
}

### Prompt

Please create a solution in cpp to the following problem:

The goal of the 8 puzzle problem is to complete pieces on $3 \times 3$ cells where one of the cells is empty space.

In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 8 as shown below.


1 3 0
4 2 5
7 8 6


You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).


1 2 3
4 5 6
7 8 0


Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Constraints

* There is a solution.

Input

The $3 \times 3$ integers denoting the pieces or space are given.

Output

Print the fewest steps in a line.

Example

Input

1 3 0
4 2 5
7 8 6


Output

4

### Response

```cpp
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 3
#define TRUE 1
#define FALSE 0

int x[4]={0,-1,0,1};
int y[4]={1,0,-1,0};
int l;
int puzzle[N][N];

void swap(int *,int *);
int abc();
int dfs(int,int,int,int);
void Solved(int,int);

int main()
{
  int i,j,sx,sy;
   
   for(i=0;i<N;i++){
     for(j=0;j<N;j++){
       scanf("%d",&puzzle[i][j]);
        if(puzzle[i][j]==0){
            sy=i;sx=j;
        }
     }
   }
   Solved(sy,sx);
   return 0;
}


void swap(int *x,int *y)
{
  int tmp;
  tmp=*x;
  *x=*y;
  *y=tmp;
}


int abc()
{
  int i,j,s=0,r;
  
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
        
        if(puzzle[i][j]==0)continue;
        
        r=puzzle[i][j]-1;
        s+=abs(r/N-i)+abs(r%N-j);
    }
  }
  return s;
}


int dfs(int d,int p,int sy,int sx)
{
  int i,m;
  int tx,ty;

  m=abc();
  
  if(m==0)return TRUE;
  if(d+m>l)return FALSE;
  
  for(i=0;i<4;i++){
    if(abs(i-p)==2)continue;
    
    tx=sx+x[i],ty=sy+y[i];
    
    if(tx<0||ty<0||tx>=N||ty>=N)continue;
    
    swap(&puzzle[ty][tx],&puzzle[sy][sx]);
    
    if(dfs(d+1,i,ty,tx))return TRUE;
    
    swap(&puzzle[ty][tx],&puzzle[sy][sx]);
  }
    return FALSE;
}


void Solved(int sy,int sx)
{
  for(l=0;;l++){
    if(dfs(0,99,sy,sx)){
      printf("%d\n",l);
      return ;
    }
  }
}

```