AT_abc271_h [ABC271Ex] General General

给你一个终点 $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$，或者判断无解。 多组数据。

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

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

- $1\le T\le 10^4$。 - $-10^9\le A,B\le 10^9$。 - $T,A,B\in Z$。