#include <iostream>
#include <unordered_map>
#include <utility>
#include <cstdlib>
#include <queue>
using namespace std;

int x, target;
unordered_map<int, int> rec[2];
queue<pair<int, bool> > Q;

int a[10];
int change(int x, int op){
	for(int i = 9; i > 0; -- i){
		a[i] = x % 10;
		x /= 10;
	}
	int p;
	for(int i = 1; i <= 9; ++ i)
		if(a[i] == 0){
			p = i;
			break;
		}
	if(op == 1){
		if(p <= 3)
			return -1;
		swap(a[p], a[p - 3]);
	}
	if(op == 2){
		if(p >= 7)
			return -1;
		swap(a[p], a[p + 3]);
	}
	if(op == 3){
		if(p % 3 == 1)
			return -1;
		swap(a[p], a[p - 1]);
	}
	if(op == 4){
		if(p % 3 == 0)
			return -1;
		swap(a[p], a[p + 1]);
	}
	x = 0;
	for(int i = 1; i <= 9; ++ i)
		x = x * 10 + a[i];
}

void check(int x, pair<int, bool> h){
	if(x != -1)
		if(rec[h.second ^ 1].count(x) == true){
			cout << rec[h.second ^ 1][x] + rec[h.second][h.first] + 1 << endl;
			exit(0);
		}
		else {
			rec[h.second][x] = rec[h.second][h.first] + 1;
			Q.push(make_pair(x, h.second));
		}
}

int main(){
	target = 123804765;
	
	cin >> x;
	if(x == target){
		cout << 0 << endl;
		return 0;
	}
	Q.push(make_pair(x, 0));
	Q.push(make_pair(x, 1));
	while(!Q.empty()){
		pair<int, bool> h = Q.front();
		cout << h.first << endl;
		Q.pop();
		for(int dir = 1; dir <= 4; ++ dir){
			int x = change(h.first, 1);
			check(x, h);
		}
	}
}