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

using Data = pair < string , int >;

int main()
{
        string S = "         ";
        queue < Data > que;
        set < string > used;
        int d[4] = {-3, -1, 1, 3};

        for ( int i = 0; i < 9; i++ ) cin >> S[i];
        
        que.emplace(S, 0);

        while ( !que.empty() ) {
                Data q = que.front(); que.pop();
                string T;
                if ( q.first == "123456780" ) {
                        cout << q.second << endl;
                        return ( 0 );
                }
                int pos = q.first.find('0');
                for ( int i = 0; i < 4; i++ ) {
                        int npos = pos + d[i];
                        string T = q.first;
                        if ( i == 1 && pos % 3 == 0 ) continue;
                        if ( i == 2 && pos % 3 == 2 ) continue;
                        if ( npos < 0 || 8 < npos ) continue;
                        swap(T[pos], T[npos]);
                        if ( used.find(T) == used.end() ) {
                                used.insert(T);
                                que.emplace(T, q.second + 1);
                        }
                }
        }

        return ( 0 );
}


### Prompt

Create a solution in CPP for 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 Data = pair < string , int >;

int main()
{
        string S = "         ";
        queue < Data > que;
        set < string > used;
        int d[4] = {-3, -1, 1, 3};

        for ( int i = 0; i < 9; i++ ) cin >> S[i];
        
        que.emplace(S, 0);

        while ( !que.empty() ) {
                Data q = que.front(); que.pop();
                string T;
                if ( q.first == "123456780" ) {
                        cout << q.second << endl;
                        return ( 0 );
                }
                int pos = q.first.find('0');
                for ( int i = 0; i < 4; i++ ) {
                        int npos = pos + d[i];
                        string T = q.first;
                        if ( i == 1 && pos % 3 == 0 ) continue;
                        if ( i == 2 && pos % 3 == 2 ) continue;
                        if ( npos < 0 || 8 < npos ) continue;
                        swap(T[pos], T[npos]);
                        if ( used.find(T) == used.end() ) {
                                used.insert(T);
                                que.emplace(T, q.second + 1);
                        }
                }
        }

        return ( 0 );
}


```