#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
#include<queue>
#include<iomanip>
#include<set>
#include<map>
#include<utility>
#include<string>
#include<vector>

using namespace std;

#define LL long long
const int dx[4] = { 1,-1,0,0 };
const int dy[4] = { 0,0,1,-1 };
bool OOA(int x, int y, int H, int W) { return (0 <= x && x<H) && (0 <= y && y<W); }

int main(){
	string f="";
	for(int i=0;i<9;i++){
		char c;
		cin>>c;
		f+=c;
	}

	map<string,int>d;
	string g="123456780";

	queue<string>q;
	q.push(f);
	d[f]=0;
	
	while(!q.empty()){
		string n=q.front();
		q.pop();
		if(n==g){
			cout<<d[n]<<endl;
			return 0;
		}
		int nd=d[n];
		for(int i=0;i<9;i++){
			if((i/3)&&(n[i]=='0'||n[i-3]=='0')){
				swap(n[i],n[i-3]);
				if(!d.count(n)){
					d[n]=nd+1;
					q.push(n);
				}
				swap(n[i],n[i-3]);
			}
			if((i%3)&&(n[i]=='0'||n[i-1]=='0')){
				swap(n[i],n[i-1]);
				if(!d.count(n)){
					d[n]=nd+1;
					q.push(n);
				}
				swap(n[i],n[i-1]);
			}
		}
	}
}


### 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
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
#include<queue>
#include<iomanip>
#include<set>
#include<map>
#include<utility>
#include<string>
#include<vector>

using namespace std;

#define LL long long
const int dx[4] = { 1,-1,0,0 };
const int dy[4] = { 0,0,1,-1 };
bool OOA(int x, int y, int H, int W) { return (0 <= x && x<H) && (0 <= y && y<W); }

int main(){
	string f="";
	for(int i=0;i<9;i++){
		char c;
		cin>>c;
		f+=c;
	}

	map<string,int>d;
	string g="123456780";

	queue<string>q;
	q.push(f);
	d[f]=0;
	
	while(!q.empty()){
		string n=q.front();
		q.pop();
		if(n==g){
			cout<<d[n]<<endl;
			return 0;
		}
		int nd=d[n];
		for(int i=0;i<9;i++){
			if((i/3)&&(n[i]=='0'||n[i-3]=='0')){
				swap(n[i],n[i-3]);
				if(!d.count(n)){
					d[n]=nd+1;
					q.push(n);
				}
				swap(n[i],n[i-3]);
			}
			if((i%3)&&(n[i]=='0'||n[i-1]=='0')){
				swap(n[i],n[i-1]);
				if(!d.count(n)){
					d[n]=nd+1;
					q.push(n);
				}
				swap(n[i],n[i-1]);
			}
		}
	}
}


```