#include<iostream>
#include<map>
#include<queue>
using namespace std;

int main(){
    map<string,int> dp;
    string g = "123456780";
    string t = "";
    for(int i = 0; i < 9; i++){
        char c; cin >> c;
        t += c;
    }
    dp[t] = 0;
    queue<string> q;
    q.push(t);
    while(!q.empty()){
        string s = q.front();   q.pop();
        int now = dp[s];
        if(s == g){
            cout << dp[s] << endl;
            return 0;
        }
        for(int i = 0; i < 9; i++){
            if(i%3==2)  continue;
            if(s[i] != '0' && s[i+1] != '0')    continue;
            swap(s[i], s[i+1]);
            if(dp.count(s) == 0){
                dp[s] = now+1;
                q.push(s);
            }
            swap(s[i], s[i+1]);
        }
        for(int i = 0; i < 6; i++){
            if(s[i] != '0' && s[i+3] != '0')    continue;
            swap(s[i], s[i+3]);
            if(dp.count(s) == 0){
                dp[s] = now+1;
                q.push(s);
            }
            swap(s[i], s[i+3]);   
        }
    }
}

### 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<iostream>
#include<map>
#include<queue>
using namespace std;

int main(){
    map<string,int> dp;
    string g = "123456780";
    string t = "";
    for(int i = 0; i < 9; i++){
        char c; cin >> c;
        t += c;
    }
    dp[t] = 0;
    queue<string> q;
    q.push(t);
    while(!q.empty()){
        string s = q.front();   q.pop();
        int now = dp[s];
        if(s == g){
            cout << dp[s] << endl;
            return 0;
        }
        for(int i = 0; i < 9; i++){
            if(i%3==2)  continue;
            if(s[i] != '0' && s[i+1] != '0')    continue;
            swap(s[i], s[i+1]);
            if(dp.count(s) == 0){
                dp[s] = now+1;
                q.push(s);
            }
            swap(s[i], s[i+1]);
        }
        for(int i = 0; i < 6; i++){
            if(s[i] != '0' && s[i+3] != '0')    continue;
            swap(s[i], s[i+3]);
            if(dp.count(s) == 0){
                dp[s] = now+1;
                q.push(s);
            }
            swap(s[i], s[i+3]);   
        }
    }
}

```