题目描述

给你一个终点 $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