#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<queue>

#include<map>

#include<cmath>

using namespace std;

int g=,a[][],n;

int dx[]= {,,,-},

          dy[]= {,-,,};

queue<int>Q;

map<int,int>v,ans;

void slove() {

    if(n==g) {

        printf("");

        exit();

    }

    Q.push(n),Q.push(g);//起始状态与终止状态同时入队

    ans[n]=,ans[g]=;

    v[g]=,v[n]=;

    while(!Q.empty()) {

        int now,cur=Q.front();

        Q.pop();

        now=cur;

        int x,y;

        for(int i=; i>=; i--)

            for(int j=; j>=; j--) {

                a[i][j]=now%,now/=;

                if(!a[i][j]) x=i,y=j;

            }

        for(int i=; i<; i++) {

            int tx=x+dx[i],ty=y+dy[i];

            if(tx<||tx>||ty>||ty<) continue;

            swap(a[tx][ty],a[x][y]);

            now=;

            for(int p=; p<=; p++)

                for(int k=; k<=; k++)

                    now=now*+a[p][k];

            if(v[now]==v[cur]) {

                swap(a[tx][ty],a[x][y]);

                continue;

            }

            if(v[now]+v[cur]==) {

                printf("%d\n",ans[now]+ans[cur]);

                exit();

            }

            ans[now]=ans[cur]+;

            v[now]=v[cur];

            Q.push(now);

            swap(a[tx][ty],a[x][y]);

        }

    }

}

int main() {

    scanf("%d",&n);

    slove();

    return ;

}