#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)


ll get(ll now,ll tc,ll tn){
	ll res = now;
	ll c = now/tc;
	c = c%10LL;
	res -= c*tc;
	res += c*tn;
	return res;
}


int main(){

	queue<ll> p,dep,zero;
	ll now=0,k;
	ll f = 123456780;
	ll ten = 100000000LL;
	FOR(i,0,9){
		cin >> k;
		now += k*ten;
		if(k==0){
			zero.push(ten);
		}
		ten /= 10LL;
	}

	//cout << now << endl;
	ll minten = 1LL;
	ll maxten = 100000000LL;

	p.push(now);
	dep.push(0);
	set<ll> se;
	se.insert(now);

	while(p.size()){
		now = p.front(); p.pop();
		ll d = dep.front(); dep.pop();
		ll t = zero.front(); zero.pop();
		if(now==f){
			cout << d << endl;
			return 0;
		}
		if(t*1000<=maxten && !se.count(get(now,t*1000,t))){
			se.insert(get(now,t*1000,t));
			p.push(get(now,t*1000,t));
			dep.push(d+1);
			zero.push(t*1000);
		}
		if(t/1000>=minten && !se.count(get(now,t/1000,t))){
			se.insert(get(now,t/1000,t));
			p.push(get(now,t/1000,t));
			dep.push(d+1);
			zero.push(t/1000);
		}
		if(t*10<=maxten && t!=100 && t!=100000 && !se.count(get(now,t*10,t))){
			se.insert(get(now,t*10,t));
			p.push(get(now,t*10,t));
			dep.push(d+1);
			zero.push(t*10);
		}
		if(t/10>=minten && t!=1000 && t!=1000000&& !se.count(get(now,t/10,t))){
			se.insert(get(now,t/10,t));
			p.push(get(now,t/10,t));
			dep.push(d+1);
			zero.push(t/10);
		}
	}
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
typedef long long ll;
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)


ll get(ll now,ll tc,ll tn){
	ll res = now;
	ll c = now/tc;
	c = c%10LL;
	res -= c*tc;
	res += c*tn;
	return res;
}


int main(){

	queue<ll> p,dep,zero;
	ll now=0,k;
	ll f = 123456780;
	ll ten = 100000000LL;
	FOR(i,0,9){
		cin >> k;
		now += k*ten;
		if(k==0){
			zero.push(ten);
		}
		ten /= 10LL;
	}

	//cout << now << endl;
	ll minten = 1LL;
	ll maxten = 100000000LL;

	p.push(now);
	dep.push(0);
	set<ll> se;
	se.insert(now);

	while(p.size()){
		now = p.front(); p.pop();
		ll d = dep.front(); dep.pop();
		ll t = zero.front(); zero.pop();
		if(now==f){
			cout << d << endl;
			return 0;
		}
		if(t*1000<=maxten && !se.count(get(now,t*1000,t))){
			se.insert(get(now,t*1000,t));
			p.push(get(now,t*1000,t));
			dep.push(d+1);
			zero.push(t*1000);
		}
		if(t/1000>=minten && !se.count(get(now,t/1000,t))){
			se.insert(get(now,t/1000,t));
			p.push(get(now,t/1000,t));
			dep.push(d+1);
			zero.push(t/1000);
		}
		if(t*10<=maxten && t!=100 && t!=100000 && !se.count(get(now,t*10,t))){
			se.insert(get(now,t*10,t));
			p.push(get(now,t*10,t));
			dep.push(d+1);
			zero.push(t*10);
		}
		if(t/10>=minten && t!=1000 && t!=1000000&& !se.count(get(now,t/10,t))){
			se.insert(get(now,t/10,t));
			p.push(get(now,t/10,t));
			dep.push(d+1);
			zero.push(t/10);
		}
	}
}

```