#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;

typedef pair<long long int, long long int> P;
long long int INF = 1e18;

int main(){
	
	queue<string> que;
	
	unordered_map<string, int> m;
	
	string fs = "";
	
	for(int i = 0; i < 9; i++){
		string s;
		cin >> s;
		fs += s;
	}
	
	que.push(fs);
	
	for(int loop = 0; loop < 1000; loop++){
		if(que.empty()){
			break;
		}
		int sz = que.size();
		for(int num = 0; num < sz; num++){
			string str = que.front();
			que.pop();
			if(m.find(str) != m.end()){
				continue;
			}
			m[str] = loop;
			for(int i = 0; i < 9; i++){
				if(str[i] == '0'){
					if(i >= 3){
						swap(str[i], str[i - 3]);
						que.push(str);
						swap(str[i], str[i - 3]);
					}
					if(i < 6){
						swap(str[i], str[i + 3]);
						que.push(str);
						swap(str[i], str[i + 3]);
					}
					if(i % 3 > 0){
						swap(str[i], str[i - 1]);
						que.push(str);
						swap(str[i], str[i - 1]);
					}
					if(i % 3 < 2){
						swap(str[i], str[i + 1]);
						que.push(str);
						swap(str[i], str[i + 1]);
					}
				}
			}
		}
	}
	
	cout << m["123456780"] << endl;
	
	return 0;
}

### Prompt

Develop a solution in Cpp 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
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;

typedef pair<long long int, long long int> P;
long long int INF = 1e18;

int main(){
	
	queue<string> que;
	
	unordered_map<string, int> m;
	
	string fs = "";
	
	for(int i = 0; i < 9; i++){
		string s;
		cin >> s;
		fs += s;
	}
	
	que.push(fs);
	
	for(int loop = 0; loop < 1000; loop++){
		if(que.empty()){
			break;
		}
		int sz = que.size();
		for(int num = 0; num < sz; num++){
			string str = que.front();
			que.pop();
			if(m.find(str) != m.end()){
				continue;
			}
			m[str] = loop;
			for(int i = 0; i < 9; i++){
				if(str[i] == '0'){
					if(i >= 3){
						swap(str[i], str[i - 3]);
						que.push(str);
						swap(str[i], str[i - 3]);
					}
					if(i < 6){
						swap(str[i], str[i + 3]);
						que.push(str);
						swap(str[i], str[i + 3]);
					}
					if(i % 3 > 0){
						swap(str[i], str[i - 1]);
						que.push(str);
						swap(str[i], str[i - 1]);
					}
					if(i % 3 < 2){
						swap(str[i], str[i + 1]);
						que.push(str);
						swap(str[i], str[i + 1]);
					}
				}
			}
		}
	}
	
	cout << m["123456780"] << endl;
	
	return 0;
}

```