#include <bits/stdc++.h>
using namespace std;
struct point{
	string s;
	string path;
	int k;
	int i;
};
string s;
unordered_map<string,bool>vis;
queue<point> q;
int jb;
void solve(){
	point p;
	p.s=s;p.i=jb;p.k=0;
	q.push(p);
	while(!q.empty()){
		p=q.front();q.pop();
		string path=p.path;
		if(vis[p.s])continue;
		if(p.s=="123456780"){
			cout<<p.k<<"\n";
//			cout<<p.path<<"\n";
			exit(0);
		}
//		cout<<p.s<<endl;
		vis[p.s]=1;
		p.k+=1;
		if(p.k==5){
			p.k=p.k;
		}
		int i=p.i;
		if(i-3>=0){
			swap(p.s[i],p.s[i-3]);
			p.i=i-3;
			p.path=path+"u";
			q.push(p);
			swap(p.s[i],p.s[i-3]);
		}
		if(i-1>=0&&i%3!=0){
			swap(p.s[i],p.s[i-1]);
			p.i=i-1;
			p.path=path+"l";
			q.push(p);
			swap(p.s[i],p.s[i-1]);
		}
		if(i+3<9){
			swap(p.s[i],p.s[i+3]);
			p.i=i+3;
			p.path=path+"d";
			q.push(p);
			swap(p.s[i],p.s[i+3]);
		}
		if(i+1<9&&(i+1)%3!=0){
			swap(p.s[i],p.s[i+1]);
			p.i=i+1;
			p.path=path+"r";
			q.push(p);
			swap(p.s[i],p.s[i+1]);
		}
	}	
}
int main(){
//	freopen("a.txt","r",stdin);
//	freopen("b.txt","w",stdout);
	char tc;
	for(int i=0;i<9;i++){
		cin>>tc;
		if(tc=='0')jb=i;
		s+=tc;
	}
	solve();
	return 0;
}

### Prompt

In cpp, your task is to solve 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;
struct point{
	string s;
	string path;
	int k;
	int i;
};
string s;
unordered_map<string,bool>vis;
queue<point> q;
int jb;
void solve(){
	point p;
	p.s=s;p.i=jb;p.k=0;
	q.push(p);
	while(!q.empty()){
		p=q.front();q.pop();
		string path=p.path;
		if(vis[p.s])continue;
		if(p.s=="123456780"){
			cout<<p.k<<"\n";
//			cout<<p.path<<"\n";
			exit(0);
		}
//		cout<<p.s<<endl;
		vis[p.s]=1;
		p.k+=1;
		if(p.k==5){
			p.k=p.k;
		}
		int i=p.i;
		if(i-3>=0){
			swap(p.s[i],p.s[i-3]);
			p.i=i-3;
			p.path=path+"u";
			q.push(p);
			swap(p.s[i],p.s[i-3]);
		}
		if(i-1>=0&&i%3!=0){
			swap(p.s[i],p.s[i-1]);
			p.i=i-1;
			p.path=path+"l";
			q.push(p);
			swap(p.s[i],p.s[i-1]);
		}
		if(i+3<9){
			swap(p.s[i],p.s[i+3]);
			p.i=i+3;
			p.path=path+"d";
			q.push(p);
			swap(p.s[i],p.s[i+3]);
		}
		if(i+1<9&&(i+1)%3!=0){
			swap(p.s[i],p.s[i+1]);
			p.i=i+1;
			p.path=path+"r";
			q.push(p);
			swap(p.s[i],p.s[i+1]);
		}
	}	
}
int main(){
//	freopen("a.txt","r",stdin);
//	freopen("b.txt","w",stdout);
	char tc;
	for(int i=0;i<9;i++){
		cin>>tc;
		if(tc=='0')jb=i;
		s+=tc;
	}
	solve();
	return 0;
}

```