#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vec;

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int calc(const vec& v){
  int res=0;
  for(int i=0;i<9;i++){
    if(v[i]==0)continue;
    int id=v[i]-1;
    res+= abs(id/3 - i/3) + abs(id%3 - i%3);
  }
  return res;
}

int main(){
  vec A(9);
  for(int i=0;i<9;i++)cin>>A[i];

  queue< vec > Q;
  map< vec , int > d;
  d[A]=0;
  Q.push(A);
  while(!Q.empty()){
    vec p=Q.front();
    Q.pop();
    
    if( calc(p)==0){
      cout<<d[p]<<endl;
      break;
    }
    
    int py=0,px=0;
    for(int i=0;i<9;i++){
      if(p[i]==0){
        py=i/3;
        px=i%3;
        break;
      }
    }

    for(int i=0;i<4;i++){
      int ny=py+dy[i];
      int nx=px+dx[i];
      if(ny<0 || ny>=3 || nx<0 || nx>=3)continue;
      vec np=p;
      swap( np[ny*3+nx] , np[py*3+px] );
      if( d.count(np) == 0 ){
        Q.push(np);
        d[np]=d[p]+1;
      }
    }
    
  }
  return 0;
}


### Prompt

In cpp, your task is to solve 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<bits/stdc++.h>
using namespace std;
typedef vector<int> vec;

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int calc(const vec& v){
  int res=0;
  for(int i=0;i<9;i++){
    if(v[i]==0)continue;
    int id=v[i]-1;
    res+= abs(id/3 - i/3) + abs(id%3 - i%3);
  }
  return res;
}

int main(){
  vec A(9);
  for(int i=0;i<9;i++)cin>>A[i];

  queue< vec > Q;
  map< vec , int > d;
  d[A]=0;
  Q.push(A);
  while(!Q.empty()){
    vec p=Q.front();
    Q.pop();
    
    if( calc(p)==0){
      cout<<d[p]<<endl;
      break;
    }
    
    int py=0,px=0;
    for(int i=0;i<9;i++){
      if(p[i]==0){
        py=i/3;
        px=i%3;
        break;
      }
    }

    for(int i=0;i<4;i++){
      int ny=py+dy[i];
      int nx=px+dx[i];
      if(ny<0 || ny>=3 || nx<0 || nx>=3)continue;
      vec np=p;
      swap( np[ny*3+nx] , np[py*3+px] );
      if( d.count(np) == 0 ){
        Q.push(np);
        d[np]=d[p]+1;
      }
    }
    
  }
  return 0;
}


```