#include<bits/stdc++.h>
#define inf 1<<29
#define linf (1e16)
#define eps (1e-8)
#define Eps (1e-12)
#define mod 1000000007
#define pi acos(-1.0)
#define phi (1.0+sqrt(5.0))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define pld(a) printf("%.10Lf\n",(ld)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define Unique(v) v.erase(unique(all(v)),v.end())
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpi;

string s = "";
string ans = "123456780";
int d[4] = {-1,1,-3,3};

typedef pair<string,pair<int,int> > state;

int solve(){
  int ind = 0;
  FOR(i,0,9)if(s[i]=='0')ind=i;
  queue<state> q;
  set<string> st;
  st.insert(s);
  q.push(mp(s,mp(0,ind)));
  while(!q.empty()){
    state u = q.front();
    q.pop();
    if(u.f==ans)return u.s.f;
    FOR(i,0,4){
      int index = u.s.s;
      if(index%3==0 && d[i]==-1)continue;
      if((index+1)%3==0 && d[i]==1)continue;
      if(index<=2 && d[i]==-3)continue;
      if(6<=index && d[i]==3)continue;
      string v = u.f;
      swap(v[index],v[index+d[i]]);
      if(st.count(v)==0){
        q.push(state(v,mp(u.s.f+1,index+d[i])));
        st.insert(v);
      }
    }
  }
  return inf;
}

int main()
{
  FOR(i,0,9){
    string a;
    cin>>a;
    s+=a;
  }
  cout<<solve()<<endl;
  return 0;
}

### Prompt

Your challenge is to write 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>
#define inf 1<<29
#define linf (1e16)
#define eps (1e-8)
#define Eps (1e-12)
#define mod 1000000007
#define pi acos(-1.0)
#define phi (1.0+sqrt(5.0))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define pld(a) printf("%.10Lf\n",(ld)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define Unique(v) v.erase(unique(all(v)),v.end())
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpi;

string s = "";
string ans = "123456780";
int d[4] = {-1,1,-3,3};

typedef pair<string,pair<int,int> > state;

int solve(){
  int ind = 0;
  FOR(i,0,9)if(s[i]=='0')ind=i;
  queue<state> q;
  set<string> st;
  st.insert(s);
  q.push(mp(s,mp(0,ind)));
  while(!q.empty()){
    state u = q.front();
    q.pop();
    if(u.f==ans)return u.s.f;
    FOR(i,0,4){
      int index = u.s.s;
      if(index%3==0 && d[i]==-1)continue;
      if((index+1)%3==0 && d[i]==1)continue;
      if(index<=2 && d[i]==-3)continue;
      if(6<=index && d[i]==3)continue;
      string v = u.f;
      swap(v[index],v[index+d[i]]);
      if(st.count(v)==0){
        q.push(state(v,mp(u.s.f+1,index+d[i])));
        st.insert(v);
      }
    }
  }
  return inf;
}

int main()
{
  FOR(i,0,9){
    string a;
    cin>>a;
    s+=a;
  }
  cout<<solve()<<endl;
  return 0;
}

```