八方向移动

题目描述

对于 $T$ 组测试用例,解决以下问题。

在 $xy$ 平面上,一枚棋子位于原点 $(0, 0)$。你可以执行以下操作任意多次(可能为 0 次):

选择一个满足 $1 \leq i \leq 8$ 且 $s_i=$ 1 的整数 $i$。设棋子当前所在位置为 $(x, y)$。

如果 $i=1$,将棋子移动到 $(x+1,y)$。

如果 $i=2$,将棋子移动到 $(x+1,y+1)$。

如果 $i=3$,将棋子移动到 $(x,y+1)$。

如果 $i=4$,将棋子移动到 $(x-1,y+1)$。

如果 $i=5$,将棋子移动到 $(x-1,y)$。

如果 $i=6$,将棋子移动到 $(x-1,y-1)$。

如果 $i=7$,将棋子移动到 $(x,y-1)$。

如果 $i=8$,将棋子移动到 $(x+1,y-1)$。

你的目标是将棋子移动到 $(A, B)$。

求达成目标所需的最小操作次数。如果不可能,输出 -1。

输入格式

输入按以下格式从标准输入给出:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

其中,$\mathrm{case}_i$ 表示第 $i$ 个测试用例。

每个测试用例按以下格式给出:

$A$ $B$ $s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8$

输出格式

共输出 $T$ 行。

第 $i$ 行应输出第 $i$ 个测试用例的答案。

样例

7
5 3 10101010
5 3 01010101
5 3 11111111
5 3 00000000
0 0 11111111
0 1 10001111
-1000000000 1000000000 10010011

8
5
5
-1
0
-1
1000000000

数据范围

• $1 \leq T \leq 10^4$
• $-10^9 \leq A,B \leq 10^9$
• $s_i$ 为 0 或 1。
• $T$、$A$、$B$ 均为整数。