在一个 的棋盘上有 个白色的马和 个黑色的马， 且有一个空位。在任何时候一个马都能按照中国象棋中马的走法移动到一个空位上。 给定一个打乱的棋盘，询问最少经过几次移动可以变成如下目标棋盘： 这里 “马” 的行棋规则与中国象棋的通常规则有所不同，一个位于 位置的马一次移动可以到达 、、、、、、 和 这些格子（有些格子可能在棋盘之外，此时不作考虑）上的任意 空 棋子，如下图所示。此外还有一个与中国象棋不同的点，就是这里的 “马” 不需要考虑 ”蹩马腿“ 的情况。

输入描述:

输入的第一行有一个正整数 ，表示一共有 组数据。接下来有 个 的矩阵， 表示白色马， 表示黑色马， 表示空位。两组数据之间没有空行。

输出描述:

对于每组数据输出一行一个整数。如果能在 步以内（包括 步）到达目标状态，则输出步数，否则输出 。