#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int> vec;
typedef vector<vec> mat;
#define N 3
int po[N*N+10];
int m2i(mat m){
  int res=0;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      res+=m[i][j]*po[i*N+j];
  return res;
}
mat i2m(int x){
  mat res(N,vec(N));;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      res[i][j]=(x%po[i*N+j+1])/po[i*N+j];
  return res;
}

signed main(){
  po[0]=1;
  for(int i=0;i<N*N;i++) po[i+1]=po[i]*10;
  mat p(N,vec(N));
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      cin>>p[i][j];
  mat e(p);
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      e[i][j]=i*N+j+1;
  e[N-1][N-1]=0;
  int ans=m2i(e);
  //cout<<ans<<endl;
  queue<int> q;
  map<int,int> m;
  q.push(m2i(p));
  m[m2i(p)]=0;
  int ax[]={1,0,-1,0};
  int ay[]={0,1,0,-1};
  while(!q.empty()){
    int x=q.front();q.pop();
    if(x==ans) break;
    //cout<<x<<endl;
    p=i2m(x);
    int zy,zx;
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
	if(p[i][j]==0) zy=i,zx=j;
    //cout<<zy<<" "<<zx<<endl;
    for(int k=0;k<4;k++){
      int ny=zy+ay[k],nx=zx+ax[k];
      if(ny<0||N<=ny||nx<0||N<=nx) continue;
      swap(p[zy][zx],p[ny][nx]);
      int t=m2i(p);
      //cout<<t<<endl;
      if(!m.count(t)){
	m[t]=m[x]+1;
	q.push(t);
      }
      swap(p[zy][zx],p[ny][nx]);
    }
  }
  cout<<m[ans]<<endl;
  return 0;
}
### Prompt

Generate 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<bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int> vec;
typedef vector<vec> mat;
#define N 3
int po[N*N+10];
int m2i(mat m){
  int res=0;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      res+=m[i][j]*po[i*N+j];
  return res;
}
mat i2m(int x){
  mat res(N,vec(N));;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      res[i][j]=(x%po[i*N+j+1])/po[i*N+j];
  return res;
}

signed main(){
  po[0]=1;
  for(int i=0;i<N*N;i++) po[i+1]=po[i]*10;
  mat p(N,vec(N));
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      cin>>p[i][j];
  mat e(p);
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      e[i][j]=i*N+j+1;
  e[N-1][N-1]=0;
  int ans=m2i(e);
  //cout<<ans<<endl;
  queue<int> q;
  map<int,int> m;
  q.push(m2i(p));
  m[m2i(p)]=0;
  int ax[]={1,0,-1,0};
  int ay[]={0,1,0,-1};
  while(!q.empty()){
    int x=q.front();q.pop();
    if(x==ans) break;
    //cout<<x<<endl;
    p=i2m(x);
    int zy,zx;
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
	if(p[i][j]==0) zy=i,zx=j;
    //cout<<zy<<" "<<zx<<endl;
    for(int k=0;k<4;k++){
      int ny=zy+ay[k],nx=zx+ax[k];
      if(ny<0||N<=ny||nx<0||N<=nx) continue;
      swap(p[zy][zx],p[ny][nx]);
      int t=m2i(p);
      //cout<<t<<endl;
      if(!m.count(t)){
	m[t]=m[x]+1;
	q.push(t);
      }
      swap(p[zy][zx],p[ny][nx]);
    }
  }
  cout<<m[ans]<<endl;
  return 0;
}
```