#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 3;
const int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};

int mat[N][N];
int lim;

int getMD(){
  int sum = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(mat[i][j] == N*N-1) continue;
      sum += abs(mat[i][j]/N-i) + abs(mat[i][j]%N-j);
    }
  }
  return sum;
}

bool IDAstar(int depth,int prev,int py,int px){
  int MD = getMD();
  if(MD == 0) return true;
  if(depth + MD > lim) return false;

  for(int k = 0; k < 4; k++){
    int ny = py + dy[k];
    int nx = px + dx[k];
    if(ny < 0 || N <= ny || nx < 0 || N <= nx) continue;
    if(abs(k - prev) == 2) continue;
    swap(mat[ny][nx],mat[py][px]);
    if(IDAstar(depth+1,k,ny,nx)) return true;
    swap(mat[ny][nx],mat[py][px]);
  }
  return false;
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int py,px;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      cin >> mat[i][j];
      if(mat[i][j] == 0){
        mat[i][j] = N*N;
        py = i;
        px = j;
      }
      mat[i][j]--;
    }
  }

  for(lim = 0; lim < 100; lim++){
    if(IDAstar(0,100,py,px)){
      cout << lim << endl;
      return 0;
    }
  }

  return 0;
}


### Prompt

Develop a solution in Cpp to the problem described below:

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

const int N = 3;
const int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};

int mat[N][N];
int lim;

int getMD(){
  int sum = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(mat[i][j] == N*N-1) continue;
      sum += abs(mat[i][j]/N-i) + abs(mat[i][j]%N-j);
    }
  }
  return sum;
}

bool IDAstar(int depth,int prev,int py,int px){
  int MD = getMD();
  if(MD == 0) return true;
  if(depth + MD > lim) return false;

  for(int k = 0; k < 4; k++){
    int ny = py + dy[k];
    int nx = px + dx[k];
    if(ny < 0 || N <= ny || nx < 0 || N <= nx) continue;
    if(abs(k - prev) == 2) continue;
    swap(mat[ny][nx],mat[py][px]);
    if(IDAstar(depth+1,k,ny,nx)) return true;
    swap(mat[ny][nx],mat[py][px]);
  }
  return false;
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int py,px;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      cin >> mat[i][j];
      if(mat[i][j] == 0){
        mat[i][j] = N*N;
        py = i;
        px = j;
      }
      mat[i][j]--;
    }
  }

  for(lim = 0; lim < 100; lim++){
    if(IDAstar(0,100,py,px)){
      cout << lim << endl;
      return 0;
    }
  }

  return 0;
}


```