当前没有测试数据。

描述

Dao 是一款简单的双人棋盘游戏，由 Jeff Pickering 和 Ben van Buskirk 于 1999 年设计。其变体 S-Dao 是一款单人游戏。在 S-Dao 中，游戏棋盘是一个 $4 \times 4$ 的正方形，共 $16$ 个格子。初始时，棋盘上随机放置 $4$ 颗黑子和 $4$ 颗白子。玩家会得到一个目标位置，并需要通过以下规则用最少的步数达到目标位置：

1. 玩家先移动一颗白子，然后移动一颗黑子，之后交替移动白子和黑子。
2. 棋子可以水平、垂直或对角线移动。每次移动时，棋子必须沿一个方向移动，直到遇到棋盘边界或另一颗棋子。不允许吃子或跳跃。
3. 每次移动时，必须移动正确颜色的棋子，不能跳过。

例如，下图展示了一个合法的移动序列，共 $4$ 步。 但如果最左侧的棋盘是初始位置，最右侧是目标位置，那么这并不是最少步数的移动序列。实际上，存在仅需 $3$ 步的移动序列。
给定初始位置和目标位置，你的任务是计算从初始位置到目标位置的最少移动步数。如果无法达到目标位置，则输出 $-1$。

输入

第一行输入测试用例的数量 $w$，$w \leq 6$。随后依次输入 $w$ 个测试用例。每个测试用例包含 $8$ 行，每行 $4$ 个字符。前 $4$ 行是初始棋盘，后 $4$ 行是目标棋盘。棋盘的第 $i$ 行表示第 $i$ 行的状态，字符 'b' 表示黑子，'w' 表示白子，'*' 表示空格。

输出

对于每个测试用例，输出一行最少移动步数。如果无法达到目标位置，则输出 $-1$。

输入数据 1

2
w**b
*wb*
*bw*
b**w
w**b
*wb*
*bw*
bw**
w**b
*b**
**b*
bwww
w**b
*bb*
****
bwww

输出数据 1

1
3

提示

如果不提前规划而直接进行简单穷举搜索，很可能会遇到问题。

来源

台湾 2004