Ex - General General Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 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) に移動させる。

あなたの目的は駒を (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

Score : 600 points

Problem Statement

Solve the following problem for T test cases.

A piece is placed at the origin (0, 0) on an xy-plane. You may perform the following operation any number of (possibly zero) times:

  • Choose an integer i such that 1 \leq i \leq 8 and s_i= 1. Let (x, y) be the current coordinates where the piece is placed.
    • If i=1, move the piece to (x+1,y).
    • If i=2, move the piece to (x+1,y+1).
    • If i=3, move the piece to (x,y+1).
    • If i=4, move the piece to (x-1,y+1).
    • If i=5, move the piece to (x-1,y).
    • If i=6, move the piece to (x-1,y-1).
    • If i=7, move the piece to (x,y-1).
    • If i=8, move the piece to (x+1,y-1).

Your objective is to move the piece to (A, B).
Find the minimum number of operations needed to achieve the objective. If it is impossible, print -1 instead.

Constraints

  • 1 \leq T \leq 10^4
  • -10^9 \leq A,B \leq 10^9
  • s_i is 0 or 1.
  • T, A, and B are integers.

Input

The input is given from Standard Input in the following format:

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

Here, \mathrm{case}_i denotes the i-th test case.

Each test case is given in the following format:

A B s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8

Output

Print T lines in total.
The i-th line should contain the answer to the i-th test case.

Sample Input 1

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

Sample Output 1

8
5
5
-1
0
-1
1000000000