#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

const int N = 4e5 + 1;

bool vis[N];
int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
std::queue<std::pair<std::vector<int>, int>> q;

int get_rank(std::vector<int> &cur) {
  int rank = 0;
  for (int i = 0; i < 9; ++i) {
    int cnt = 0;
    for (int j = i + 1; j < 9; ++j) {
      if (cur[j] < cur[i]) cnt ++;
    }
    rank += cnt * fac[8 - i];
  }
  return rank;
}

void extend(std::vector<int> &cur, int pos, int step, int opr, int opc) {
  auto nxt = cur;
  int r = pos / 3;
  int c = pos % 3;
  int nr = r + opr;
  int nc = c + opc;
  if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3) {
    int np = nr * 3 + nc;
    std::swap(nxt[pos], nxt[np]);
    int rank = get_rank(nxt);
    if (!vis[rank]) {
      q.push({nxt,  step + 1});
      vis[rank] = 1;
    }

  }
}

int main() {
  while (!q.empty()) q.pop();
  memset(vis, 0, sizeof(vis));
  std::vector<int> goal = {1, 2, 3, 4, 5, 6, 7, 8, 0};
  int target = get_rank(goal);
  std::vector<int> st(9);
  for (int i = 0; i < 9; ++i) std::cin >> st[i];
  q.push({st, 0});
  vis[get_rank(st)] = 1;
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();
    auto p = cur.first;
    int step = cur.second;
    if (get_rank(p) == target) {
      std::cout << step << std::endl;
      return 0;
    }
    if (step + 1 > 45) continue;
    int pos;
    for (int i = 0; i < 9; ++i) {
      if (p[i] == 0) pos = i;
    }
    extend(p, pos, step, 0, 1);
    extend(p, pos, step, 0, -1);
    extend(p, pos, step, 1, 0);
    extend(p, pos, step, -1, 0);
  }
  return 0;
}


### Prompt

Your task is to create 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 <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

const int N = 4e5 + 1;

bool vis[N];
int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
std::queue<std::pair<std::vector<int>, int>> q;

int get_rank(std::vector<int> &cur) {
  int rank = 0;
  for (int i = 0; i < 9; ++i) {
    int cnt = 0;
    for (int j = i + 1; j < 9; ++j) {
      if (cur[j] < cur[i]) cnt ++;
    }
    rank += cnt * fac[8 - i];
  }
  return rank;
}

void extend(std::vector<int> &cur, int pos, int step, int opr, int opc) {
  auto nxt = cur;
  int r = pos / 3;
  int c = pos % 3;
  int nr = r + opr;
  int nc = c + opc;
  if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3) {
    int np = nr * 3 + nc;
    std::swap(nxt[pos], nxt[np]);
    int rank = get_rank(nxt);
    if (!vis[rank]) {
      q.push({nxt,  step + 1});
      vis[rank] = 1;
    }

  }
}

int main() {
  while (!q.empty()) q.pop();
  memset(vis, 0, sizeof(vis));
  std::vector<int> goal = {1, 2, 3, 4, 5, 6, 7, 8, 0};
  int target = get_rank(goal);
  std::vector<int> st(9);
  for (int i = 0; i < 9; ++i) std::cin >> st[i];
  q.push({st, 0});
  vis[get_rank(st)] = 1;
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();
    auto p = cur.first;
    int step = cur.second;
    if (get_rank(p) == target) {
      std::cout << step << std::endl;
      return 0;
    }
    if (step + 1 > 45) continue;
    int pos;
    for (int i = 0; i < 9; ++i) {
      if (p[i] == 0) pos = i;
    }
    extend(p, pos, step, 0, 1);
    extend(p, pos, step, 0, -1);
    extend(p, pos, step, 1, 0);
    extend(p, pos, step, -1, 0);
  }
  return 0;
}


```