#include<bits/stdc++.h>
using namespace std;
const int il=10007;
int hy[]={1,0};
int zy[]={0,1};
int goal=123804756;
struct node{
	int num,id;
};
node fir;
int cnt,fa[10000000];
vector<node> Hash[il];
void bfs(){
	queue<node> q;
	q.push(fir);
	while(!q.empty()){
		node h=q.front();q.pop();
		for(int i=1;i<=9;i++){
			int nowh=(i-1)/3+1;
			int nowz=i-(nowh-1)*3;
			int nowch=pow(10,(9-i));
			int nownum=h.num/nowch%10;
			for(int j=0;j<=1;j++){
				int nexth=nowh+hy[j];
				int nextz=nowz+zy[j];
				if(nexth<1||nextz<1||nexth>3||nextz>3) continue;
				node will=h;
				if(j==0){
					int willch=nowch/1000;
					int willnum=h.num/willch%10;
					will.num=will.num-nownum*nowch-willnum*willch+nownum*willch+willnum*nowch;
				}
				else{
					int willch=nowch/10;
					int willnum=h.num/willch%10;
					will.num=will.num-nownum*nowch-willnum*willch+nownum*willch+willnum*nowch;
				}
				int pnum=will.num%il;
				if(!Hash[pnum].empty()){
					bool flag=false;
					for(int k=0;k<Hash[pnum].size();k++){
						if(Hash[pnum][k].num==will.num){
							flag=true;
							break;
						}
					}
					if(flag) continue;
				}
				Hash[pnum].push_back(will);
				will.id=++cnt;
				fa[will.id]=h.id;
				if(will.num==goal) return;
				q.push(will);
			}
		}
	}
}
int main(){
	cin>>fir.num;
	fir.id=++cnt;
	Hash[fir.num%il].push_back(fir);
	bfs();
	int ans=1;
	int t=cnt;
	while(t!=1){
		t=fa[t];
		ans++;
	}
	cout<<ans;
}

#include<bits/stdc++.h> using namespace std; const int il=10007; int hy[]={1,0}; int zy[]={0,1}; int goal=123804756; struct node{ int num,id; }; node fir; int cnt,fa[10000000]; vector Hash[il]; void bfs(){ queue q; q.push(fir); while(!q.empty()){ node h=q.front();q.pop(); for(int i=1;i<=9;i++){ int nowh=(i-1)/3+1; int nowz=i-(nowh-1)3; int nowch=pow(10,(9-i)); int nownum=h.num/nowch%10; for(int j=0;j<=1;j++){ int nexth=nowh+hy[j]; int nextz=nowz+zy[j]; if(nexth<1||nextz<1||nexth>3||nextz>3) continue; node will=h; if(j==0){ int willch=nowch/1000; int willnum=h.num/willch%10; will.num=will.num-nownumnowch-willnumwillch+nownumwillch+willnumnowch; } else{ int willch=nowch/10; int willnum=h.num/willch%10; will.num=will.num-nownumnowch-willnumwillch+nownumwillch+willnum*nowch; } int pnum=will.num%il; if(!Hash[pnum].empty()){ bool flag=false; for(int k=0;k<Hash[pnum].size();k++){ if(Hash[pnum][k].num==will.num){ flag=true; break; } } if(flag) continue; } Hash[pnum].push_back(will); will.id=++cnt; fa[will.id]=h.id; if(will.num==goal) return; q.push(will); } } } } int main(){ cin>>fir.num; fir.id=++cnt; Hash[fir.num%il].push_back(fir); bfs(); int ans=1; int t=cnt; while(t!=1){ t=fa[t]; ans++; } cout<<ans; }