题目描述

给你一个 \(n\) 行 \(m\) 列的网格，网格的每个位置用坐标 \(\left(x, y\right)\) 表示（\(x\) 为行号， \(y\) 为列号，均从 \(1\) 开始计数）。在网格的起始位置 \(\left(s_x, s_y\right)\) 处放置一个标准的正方体骰子，骰子的六个面分别标记有颜色 \(c_1, c_2, \dots, c_6\)，六个面的位置定义如下：

• \(c_1\)：骰子的顶面（朝上）
• \(c_2\)：骰子的前面（即网格的行号增大方向）
• \(c_3\)：骰子的右面（朝向网格的列号增大方向）
• \(c_4\)：骰子的左面（朝向网格的列号减小方向）
• \(c_5\)：骰子的后面（朝向网格的行号减小方向）
• \(c_6\)：骰子的底面（朝下，接触网格）

骰子每次可以在网格内向上、向下、向左、向右四个方向滚动一个单位，每次滚动后，骰子会以接触网格的棱为轴旋转，六个面的朝向会相应改变。而骰子每停留在一个网格格子上，会将该格子染色为此时骰子底面的颜色；若同一个格子被多次经过，最终颜色以最后一次停留时的底面颜色为准。

请你计算要让网格的目标位置 \(\left(t_x, t_y\right)\) 的最终颜色恰好为指定颜色 \(c_t\) （\(c_t\) 是骰子初始六个面颜色中的某一种）时，骰子需要滚动的最小次数。

输入格式

第一行输入一个整数 \(T\) 表示测试数据组数。

对于每组数据：输入的第一行包含两个整数 \(n, m\)。

输入的第二行包含六个整数 \(c_1 \sim c_6\)，表示六个面的颜色。

输入的第三行包含五个整数 \(s_x, s_y, t_x, t_y, c_t\)。

\(1 \le T \le 5\)

对于每组数据： \(2 \le n, m \le 300, 1 \le c_i \le 6, 1 \le s_x \le n, 1 \le s_y \le m, 1 \le t_x \le n, 1 \le t_y \le m, 1 \le c_t \le 6\)

输出格式

每组输出只包括一个整数，为骰子的最小滚动次数；若不能将目标位置染成规定颜色，则输出 \(-1\)。

样例输入

1
2 2
1 2 3 4 5 6
1 1 2 2 2

样例输出

2

提示

骰子从 \(\left(1, 1\right)\) 先向右滚动到 \(\left(1, 2\right)\) （次数 \(1\)，此时底面变为 \(c_3 = 3\)），再向下滚动到 \(\left(2, 2\right)\) （次数 \(2\)，此时底面变成 \(c_2 = 2\)）标位置颜色为 2。可以证明，这是骰子的最小滚动次数。