{"problem":{"name":"Ex - General General","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc271_h"},"statements":[{"statement_type":"Markdown","content":"Solve the following problem for $T$ test cases.\nA piece is placed at the origin $(0, 0)$ on an $xy$\\-plane. You may perform the following operation any number of (possibly zero) times:\n\n*   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.\n    *   If $i=1$, move the piece to $(x+1,y)$.\n    *   If $i=2$, move the piece to $(x+1,y+1)$.\n    *   If $i=3$, move the piece to $(x,y+1)$.\n    *   If $i=4$, move the piece to $(x-1,y+1)$.\n    *   If $i=5$, move the piece to $(x-1,y)$.\n    *   If $i=6$, move the piece to $(x-1,y-1)$.\n    *   If $i=7$, move the piece to $(x,y-1)$.\n    *   If $i=8$, move the piece to $(x+1,y-1)$.\n\nYour objective is to move the piece to $(A, B)$.  \nFind the minimum number of operations needed to achieve the objective. If it is impossible, print `-1` instead.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^4$\n*   $-10^9 \\leq A,B \\leq 10^9$\n*   $s_i$ is `0` or `1`.\n*   $T$, $A$, and $B$ are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nHere, $\\mathrm{case}_i$ denotes the $i$\\-th test case.\nEach test case is given in the following format:\n\n$A$ $B$ $s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc271_h","tags":[],"sample_group":[["7\n5 3 10101010\n5 3 01010101\n5 3 11111111\n5 3 00000000\n0 0 11111111\n0 1 10001111\n-1000000000 1000000000 10010011","8\n5\n5\n-1\n0\n-1\n1000000000"]],"created_at":"2026-03-03 11:01:13"}}