#include <iostream>
#include <cmath>

using namespace std;

int limit=0,T[3][3];

int evaluate(){
  int cx[]={2,0,1,2,0,1,2,0,1},cy[]={2,0,0,0,1,1,1,2,2};
  int ret=0;
  for (int i=0;i<3;i++){
    for (int j=0;j<3;j++){
      int ti = T[i][j];
      if (ti==0)continue;
      ret+=abs(cx[ti]-j);
      ret+=abs(cy[ti]-i);
      // if (cx[ti]!=j||cy[ti]!=i)ret++;
    }
  }
  return ret;
}

bool trymove(int c,int zx,int zy,int pzx,int pzy){
  int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
  if (evaluate()==0)return true;
  if (c+evaluate()>limit)return false;
  for (int i=0;i<4;i++){
    if (0>zx+dx[i]||zx+dx[i]>2||0>zy+dy[i]||zy+dy[i]>2)continue;
    if (zx+dx[i]==pzx&&zy+dy[i]==pzy)continue;
    swap(T[zy][zx],T[zy+dy[i]][zx+dx[i]]);
    if (trymove(c+1,zx+dx[i],zy+dy[i],zx,zy)) return true;
    swap(T[zy][zx],T[zy+dy[i]][zx+dx[i]]);
  }
  return false;
}

int main(){
  int zx,zy;
  for (int i=0;i<3;i++){
    for (int j=0;j<3;j++){
      cin >> T[i][j];
      if (T[i][j]==0){
	zx=j;
	zy=i;
      }
    }
  }
  
  while (evaluate()){
    limit++;
    if (trymove(0,zx,zy,zx,zy))break;
  }
  
  cout << limit << endl;
  
  return 0;
}
### Prompt

Construct a cpp code solution to the problem outlined:

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>

using namespace std;

int limit=0,T[3][3];

int evaluate(){
  int cx[]={2,0,1,2,0,1,2,0,1},cy[]={2,0,0,0,1,1,1,2,2};
  int ret=0;
  for (int i=0;i<3;i++){
    for (int j=0;j<3;j++){
      int ti = T[i][j];
      if (ti==0)continue;
      ret+=abs(cx[ti]-j);
      ret+=abs(cy[ti]-i);
      // if (cx[ti]!=j||cy[ti]!=i)ret++;
    }
  }
  return ret;
}

bool trymove(int c,int zx,int zy,int pzx,int pzy){
  int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
  if (evaluate()==0)return true;
  if (c+evaluate()>limit)return false;
  for (int i=0;i<4;i++){
    if (0>zx+dx[i]||zx+dx[i]>2||0>zy+dy[i]||zy+dy[i]>2)continue;
    if (zx+dx[i]==pzx&&zy+dy[i]==pzy)continue;
    swap(T[zy][zx],T[zy+dy[i]][zx+dx[i]]);
    if (trymove(c+1,zx+dx[i],zy+dy[i],zx,zy)) return true;
    swap(T[zy][zx],T[zy+dy[i]][zx+dx[i]]);
  }
  return false;
}

int main(){
  int zx,zy;
  for (int i=0;i<3;i++){
    for (int j=0;j<3;j++){
      cin >> T[i][j];
      if (T[i][j]==0){
	zx=j;
	zy=i;
      }
    }
  }
  
  while (evaluate()){
    limit++;
    if (trymove(0,zx,zy,zx,zy))break;
  }
  
  cout << limit << endl;
  
  return 0;
}
```