#include <stdio.h>
#include<memory.h>
#define len 362888
#define le 9
typedef int state[le];
state st[len],goal;
int dis[len],fact[le],head[len],vis[len],der[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
void encode()
{
    int i;
    for(i=fact[0]=1; i<le; i++)
        fact[i]=fact[i-1]*i;
}
int decode(int s)
{
    int i,j,code,cnt;
    for(i=code=0; i<le; i++)
    {
        for(cnt=0,j=i+1; j<le; j++)    if(st[s][i]>st[s][j])     cnt++;
        code+=cnt*fact[8-i];
    }
    if(vis[code])   return 0;
    else            return vis[code]=1;
}
int bfs()
{
    int front=1,rear=2,i,x,y,z,nx,ny,nz;
    encode();
    while(front<rear)
    {
        state& s=st[front];
        if(memcmp(s,goal,sizeof(s))==0)
            return front;
        for(i=0; i<le; i++)
            if(s[i]==0)     break;
        x=i/3;
        y=i%3;
        z=i;
        for(i=0; i<4; i++)
        {

            nx=x+der[i][0];
            ny=y+der[i][1];
            nz=nx*3+ny;
            if(nx>=0&&nx<3&&ny>=0&&ny<3)
            {
                state& t=st[rear];
                memcpy(&t,&s,sizeof(s));
                t[z]=s[nz];
                t[nz]=s[z];
                dis[rear]=dis[front]+1;
                if(decode(rear))
                    rear++;
            }
        }
        front++;
    }
    return 0;
}
int main(void)
{
    int i,oj;
    int ppp = 1;
    for(i=0; i<le; i++)   scanf("%d",&st[1][i]);
    for(i=0; i<le; i++){
        goal[i] = ppp;
        ppp++;
    }
    goal[8] = 0;

    //for(i=0; i<le; i++)   scanf("%d",&goal[i]);
    oj=bfs();
    if(oj)    printf("%d\n",dis[oj]);
    else    puts("Impossible");
    return 0;
}


### Prompt

Please formulate a Cpp solution to the following problem:

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 <stdio.h>
#include<memory.h>
#define len 362888
#define le 9
typedef int state[le];
state st[len],goal;
int dis[len],fact[le],head[len],vis[len],der[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
void encode()
{
    int i;
    for(i=fact[0]=1; i<le; i++)
        fact[i]=fact[i-1]*i;
}
int decode(int s)
{
    int i,j,code,cnt;
    for(i=code=0; i<le; i++)
    {
        for(cnt=0,j=i+1; j<le; j++)    if(st[s][i]>st[s][j])     cnt++;
        code+=cnt*fact[8-i];
    }
    if(vis[code])   return 0;
    else            return vis[code]=1;
}
int bfs()
{
    int front=1,rear=2,i,x,y,z,nx,ny,nz;
    encode();
    while(front<rear)
    {
        state& s=st[front];
        if(memcmp(s,goal,sizeof(s))==0)
            return front;
        for(i=0; i<le; i++)
            if(s[i]==0)     break;
        x=i/3;
        y=i%3;
        z=i;
        for(i=0; i<4; i++)
        {

            nx=x+der[i][0];
            ny=y+der[i][1];
            nz=nx*3+ny;
            if(nx>=0&&nx<3&&ny>=0&&ny<3)
            {
                state& t=st[rear];
                memcpy(&t,&s,sizeof(s));
                t[z]=s[nz];
                t[nz]=s[z];
                dis[rear]=dis[front]+1;
                if(decode(rear))
                    rear++;
            }
        }
        front++;
    }
    return 0;
}
int main(void)
{
    int i,oj;
    int ppp = 1;
    for(i=0; i<le; i++)   scanf("%d",&st[1][i]);
    for(i=0; i<le; i++){
        goal[i] = ppp;
        ppp++;
    }
    goal[8] = 0;

    //for(i=0; i<le; i++)   scanf("%d",&goal[i]);
    oj=bfs();
    if(oj)    printf("%d\n",dis[oj]);
    else    puts("Impossible");
    return 0;
}


```