#include <vector>
#include <algorithm>
#include <cstdlib>
#include <complex>
#include <iostream>
#include<queue>
#include <map>
using namespace std;
const int MX = 100007;
const int MXN = 362887;
	const long double pi = acos(-1);

	int main(){
		int omar = 0;

		while (true)
		{int done = 0;
			omar++;

			map <string, int> vis;
			char c;
			string a;
			cin >> c;
			int y = c - '0';
			cin >> a;
			if (a == "000000000")return 0;
			queue <string > Q;
			Q.push(a);
			vis[a] = 0;
			string tst = "123456789";
			bool cmp = 0;
			while (!Q.empty()){
				done++;
				if (done >= 1677216)break;
				string m = Q.front();
				Q.pop();
				if (vis[tst] != 0)break;
				string z = m;
				swap(z[0], z[1]);
				swap(z[3], z[4]);
				swap(z[0], z[4]);
				if (vis[z] == 0){//1
					vis[z] = vis[m] + 1;

					Q.push(z);
					if (vis[z] == y)cmp = 1;

				}z = m;
				swap(z[0], z[1]);
				swap(z[3], z[4]);
				swap(z[1], z[3]);
				if (vis[z] == 0){//1
					vis[z] = vis[m] + 1;
					Q.push(z);

					if (vis[z] == y)cmp = 1;
				}
				z = m;
				swap(z[1], z[2]);
				swap(z[5], z[4]);
				swap(z[5], z[1]);
				if (vis[z] == 0){//2
					vis[z] = vis[m] + 1;
					Q.push(z);

					if (vis[z] == y)cmp = 1;
				}
				z = m;
				swap(z[1], z[2]);
				swap(z[5], z[4]);
				swap(z[4], z[2]);
				if (vis[z] == 0){//2
					vis[z] = vis[m] + 1;
					Q.push(z);

					if (vis[z] == y)cmp = 1;
				}
				z = m;
				swap(z[3], z[4]);
				swap(z[6], z[7]);
				swap(z[4], z[6]);
				if (vis[z] == 0){//3
					vis[z] = vis[m] + 1;
					Q.push(z);

					if (vis[z] == y)cmp = 1;
				}
				z = m;
				swap(z[3], z[4]);
				swap(z[6], z[7]);
				swap(z[7], z[3]);
				if (vis[z] == 0){//3
					vis[z] = vis[m] + 1;
					Q.push(z);

					if (vis[z] == y)cmp = 1;
				}
				z = m;

				swap(z[5], z[4]);
				swap(z[8], z[7]);
				swap(z[4], z[8]);
				if (vis[z] == 0){//4
					vis[z] = vis[m] + 1;
					Q.push(z);

					if (vis[z] == y)cmp = 1;
				}
				z = m;
				swap(z[5], z[4]);
				swap(z[8], z[7]);
				swap(z[7], z[5]);
				if (vis[z] == 0){//4
					vis[z] = vis[m] + 1;
					Q.push(z);

					if (vis[z] == y)cmp = 1;
				}
				if (cmp)break;

			}
			if (vis[tst]){
				if (vis[tst] <= y)cout << vis[tst];
			}
			else{
				if (tst == a)cout << 0;
				else cout<<-1;
			}

			cout << endl;
		}
	}