#include<bits/stdc++.h>
using namespace std;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i,n) for(UL i=0; i<(n); i++)

UL E[9][9]={
 {0,1,0,1,0,0,0,0,0},
 {1,0,1,0,1,0,0,0,0},
 {0,1,0,0,0,1,0,0,0},
 {1,0,0,0,1,0,1,0,0},
 {0,1,0,1,0,1,0,1,0},
 {0,0,1,0,1,0,0,0,1},
 {0,0,0,1,0,0,0,1,0},
 {0,0,0,0,1,0,1,0,1},
 {0,0,0,0,0,1,0,1,0}
};

int main() {
 set<string> G;
 string S(9,' '); rep(i,9) scanf(" %c",&S[i]);
 queue<pair<string,UL>> Q; Q.push({S,0});
 while(Q.size()){
  string P=move(Q.front().first);
  UL d=Q.front().second;
  UL p=P.find('0');
  Q.pop();
  if(P=="123456780"){cout<<d<<endl; break;}
  if(G.count(P)) continue;
  G.insert(P);
  rep(j,9) {
   if(!E[p][j]) continue;
   swap(P[p],P[j]);
   Q.push({P,d+1});
   swap(P[p],P[j]);
  }
 }
 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;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i,n) for(UL i=0; i<(n); i++)

UL E[9][9]={
 {0,1,0,1,0,0,0,0,0},
 {1,0,1,0,1,0,0,0,0},
 {0,1,0,0,0,1,0,0,0},
 {1,0,0,0,1,0,1,0,0},
 {0,1,0,1,0,1,0,1,0},
 {0,0,1,0,1,0,0,0,1},
 {0,0,0,1,0,0,0,1,0},
 {0,0,0,0,1,0,1,0,1},
 {0,0,0,0,0,1,0,1,0}
};

int main() {
 set<string> G;
 string S(9,' '); rep(i,9) scanf(" %c",&S[i]);
 queue<pair<string,UL>> Q; Q.push({S,0});
 while(Q.size()){
  string P=move(Q.front().first);
  UL d=Q.front().second;
  UL p=P.find('0');
  Q.pop();
  if(P=="123456780"){cout<<d<<endl; break;}
  if(G.count(P)) continue;
  G.insert(P);
  rep(j,9) {
   if(!E[p][j]) continue;
   swap(P[p],P[j]);
   Q.push({P,d+1});
   swap(P[p],P[j]);
  }
 }
 return 0;
}


```