配点 : $600$ 点

問題文

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

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