Eight puzzle

Time limit1sMemory limit256 MB

Summary

Find the fewest slides that turn each given 3 by 3 board into the goal layout, or report impossible.

Level: Medium6 of 10
Topics: BFS, Shortest path, Graph
Solved: No attempts yet

Problem

A 3 by 3 board holds eight square pieces numbered 1 to 8 and one open slot. One move slides a piece that shares an edge with the open slot into that slot.

Given a scrambled board, arrange the pieces into this configuration:

123
456
78#

Here # is the open slot. Write a program that reports the minimum number of moves for each board, and reports that the goal cannot be reached when no sequence of moves gets there.

Input

The first line contains the number of test cases $n$ ( $1 \le n \le 100$ ). A blank line follows.

Each test case is three lines describing the starting board, and each line holds three symbols. A blank line separates consecutive test cases. Every board contains the symbols 1 through 8 and # exactly once, and # is the open slot.

Output

For each test case, print the minimum number of moves on its own line. Print impossible when the goal cannot be reached.

Examples2

Example 1

Input

Expected output

2
impossible

Example 2
Input
```
1

123
456
78#
```
Expected output
```
0
```