题目描述

$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$ 番目のテストケースに対する答えを出力せよ。

题目大意

题目描述

给你一个终点 $G(A,B)$ 和一个向量集合 $S\subset S'=\{(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)\}$。初始有一个点 $P(0,0)$。每次你可以选择一个向量 $V\in S$，然后执行 $P\gets P+V$。求出在最优策略下执行几次可以使得 $P=G$，或者判断无解。

多组数据。

数据范围

• $1\le T\le 10^4$。

• $-10^9\le A,B\le 10^9$。

• $T,A,B\in Z$。

输入格式

第一行输入一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个整数 $A,B$ 和一个长为 $8$ 的 $\texttt{0/1}$ 字符串 $s$。如果 $s_i=1$ 则表示 $S$ 中存在 $S'$ 中的第 $i$ 个元素。

输出格式

对于每个测试用例，输出答案。

translated_by_nr0728

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$ は整数