#include<bits/stdc++.h>
using namespace std;
typedef pair<string,int> P;
queue<P > que;
void move(string st,int x){
  int pos;
  int look[4]={-3,3,-1,1};//up do le ri
  for(int i=0;i<9;i++){
    if(st[i]=='0'){
      pos=i;
      break;
    }
  }
  for(int i=0;i<4;i++){
    string str=st;
    if(i==2&&pos%3==0)continue;
    if(i==3&&pos%3==2)continue;
    int npos=pos+look[i];
    if(npos>8||npos<0)continue;
    swap(str[pos],str[npos]);
    que.push(P(str,x+1));
  }
}
int main(){
  string puzzle="";
  string goal="123456780";
  map<string,bool> ma;
  for(int i=0;i<9;i++){
    int x;
    cin >> x;
    puzzle+='0'+x;
  }
  que.push(P(puzzle,0));
  while(1){
    P p=que.front();que.pop();
    string puz=p.first;
    int x=p.second;
    if(puz==goal){
      cout << x << endl;
      break;
    }
    if(ma[puz])continue;
    else ma[puz]=1;
    move(puz,x);
  }
  return 0;
}
### Prompt

Your task is to create 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;
typedef pair<string,int> P;
queue<P > que;
void move(string st,int x){
  int pos;
  int look[4]={-3,3,-1,1};//up do le ri
  for(int i=0;i<9;i++){
    if(st[i]=='0'){
      pos=i;
      break;
    }
  }
  for(int i=0;i<4;i++){
    string str=st;
    if(i==2&&pos%3==0)continue;
    if(i==3&&pos%3==2)continue;
    int npos=pos+look[i];
    if(npos>8||npos<0)continue;
    swap(str[pos],str[npos]);
    que.push(P(str,x+1));
  }
}
int main(){
  string puzzle="";
  string goal="123456780";
  map<string,bool> ma;
  for(int i=0;i<9;i++){
    int x;
    cin >> x;
    puzzle+='0'+x;
  }
  que.push(P(puzzle,0));
  while(1){
    P p=que.front();que.pop();
    string puz=p.first;
    int x=p.second;
    if(puz==goal){
      cout << x << endl;
      break;
    }
    if(ma[puz])continue;
    else ma[puz]=1;
    move(puz,x);
  }
  return 0;
}
```