#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
queue<pair<string,int> > Q;

void Sw(string st,int x)
{
	int i;
	int pos,npos;
	int d[4]={-3,3,-1,1};
	string st1;
	
	for(i=0;i<=8;i++)
	{
		if(st[i]=='0')
		{
			pos=i;
			break;
		}
	}
	for(i=0;i<=3;i++)
	{
		st1=st;
		if(i==2 && pos%3==0) continue;
		if(i==3 && pos%3==2) continue;
		npos=pos+d[i];
		if(npos>=9 || npos<=-1) continue;
		swap(st1[pos],st1[npos]);
		Q.push(pair<string,int>(st1,x+1));
	}
}

int main()
{
	string puzzle="";
	string goal="123456780";
	map<string,bool> M;
	int i,x;
	string P;
	
	for(i=0;i<=8;i++)
	{
		cin >> x;
		puzzle+='0'+x;
	}
	Q.push(pair<string,int>(puzzle,0));
	while(1)
	{
		pair<string,int> p=Q.front();
		Q.pop();
		P=p.first;
		x=p.second;
		if(P==goal)
		{
			cout << x << endl;
			break;
		}
		if(M[P]) continue;
		else M[P]=1;
		Sw(P,x);
	}
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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<cstdio>
#include<queue>
#include<map>
using namespace std;
queue<pair<string,int> > Q;

void Sw(string st,int x)
{
	int i;
	int pos,npos;
	int d[4]={-3,3,-1,1};
	string st1;
	
	for(i=0;i<=8;i++)
	{
		if(st[i]=='0')
		{
			pos=i;
			break;
		}
	}
	for(i=0;i<=3;i++)
	{
		st1=st;
		if(i==2 && pos%3==0) continue;
		if(i==3 && pos%3==2) continue;
		npos=pos+d[i];
		if(npos>=9 || npos<=-1) continue;
		swap(st1[pos],st1[npos]);
		Q.push(pair<string,int>(st1,x+1));
	}
}

int main()
{
	string puzzle="";
	string goal="123456780";
	map<string,bool> M;
	int i,x;
	string P;
	
	for(i=0;i<=8;i++)
	{
		cin >> x;
		puzzle+='0'+x;
	}
	Q.push(pair<string,int>(puzzle,0));
	while(1)
	{
		pair<string,int> p=Q.front();
		Q.pop();
		P=p.first;
		x=p.second;
		if(P==goal)
		{
			cout << x << endl;
			break;
		}
		if(M[P]) continue;
		else M[P]=1;
		Sw(P,x);
	}
	return 0;
}
```