时间限制：1秒　　内存限制：256M

---

【题目描述】

　　编号为 1..8 的 8 个正方形滑块被摆成 3 行 3 列（有一个格子留空），如图所示。每次可以把与空格相邻的滑块（有公共边才算相邻）移到空格中，而它原来的位置就成为一个新空格。给定初始局面和目标局面（用 0 表示空格），你的任务是计算出最少的移动步骤。如果无法到达目标局面，则输出 -1。

【输入格式】

　　第一行一个整数T，表示有 \(T\) 组数据：每组数据占一行，包含两个数字串，第一个为初始局面，第二个为目标局面。

【输出格式】

　　每组数据为一个整数，表示最少的变换步骤，数据保证一定有解。

【输入输出样例】

　Input

2
281463750 123804765
264137058 815736402

　Output

12
31

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤T≤10\)。

【来源】

　　Mr.he