题目描述

解决以下问题的 $T$ 个测试用例。

在 $xy$ 平面上的原点 $(0, 0)$ 上放置了一个棋子。您可以执行以下操作任意次数（包括零次）：

• 选择一个整数 $i$，满足 $1 \\leq i \\leq 8$ 且 $s_i=$ 1。设 $(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。

约束条件

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

输入

输入以以下格式从标准输入给出：

$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$ 个测试用例的答案。

示例输入 1

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

示例输出 1

8
5
5
-1
0
-1
1000000000