#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
 
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
 
int t[3][3];
int limit;
 
int getHeuri(){
  int res=0,a;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      if(t[i][j]==0)continue;
      a=t[i][j]-1;
      res+=abs(a/3-i)+abs(a%3-j);
    }
  }
  return res;
}
 
bool check(int depth,int prev,int py,int px){
  int heuri=getHeuri();
  if(heuri+depth>limit)return false;
  if(heuri==0)return true;
  for(int i=0;i<4;i++){
    if(abs(i-prev)==2)continue;
    int ny=py+dy[i],nx=px+dx[i];
    if(ny<0||nx<0)continue;
    if(ny>=3||nx>=3)continue;
    swap(t[ny][nx],t[py][px]);
    if(check(depth+1,i,ny,nx)) return true;
    swap(t[ny][nx],t[py][px]);
  }
  return false;
}
 
void solve(int py,int px){
  for(limit=0;;limit++){
    if(check(0,99,py,px)){
      cout<<limit<<endl;
      return;
    }
  }
}
 
int main(){
  int py,px;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>t[i][j];
      if(t[i][j]==0){
    py=i;
    px=j;
      }
    }
  }
  solve(py,px);
  return 0;
}
### Prompt

Your challenge is to write a Cpp solution 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<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
 
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
 
int t[3][3];
int limit;
 
int getHeuri(){
  int res=0,a;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      if(t[i][j]==0)continue;
      a=t[i][j]-1;
      res+=abs(a/3-i)+abs(a%3-j);
    }
  }
  return res;
}
 
bool check(int depth,int prev,int py,int px){
  int heuri=getHeuri();
  if(heuri+depth>limit)return false;
  if(heuri==0)return true;
  for(int i=0;i<4;i++){
    if(abs(i-prev)==2)continue;
    int ny=py+dy[i],nx=px+dx[i];
    if(ny<0||nx<0)continue;
    if(ny>=3||nx>=3)continue;
    swap(t[ny][nx],t[py][px]);
    if(check(depth+1,i,ny,nx)) return true;
    swap(t[ny][nx],t[py][px]);
  }
  return false;
}
 
void solve(int py,int px){
  for(limit=0;;limit++){
    if(check(0,99,py,px)){
      cout<<limit<<endl;
      return;
    }
  }
}
 
int main(){
  int py,px;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>t[i][j];
      if(t[i][j]==0){
    py=i;
    px=j;
      }
    }
  }
  solve(py,px);
  return 0;
}
```