06769. USACO·变换数对 未做

回答 $Q$（$1\le Q\le 10^5$）个独立查询，每个查询的形式如下：

给定四个整数 $a$，$b$，$c$，$d$（$-10^{18}\le a,b,c,d\le 10^{18}$）。在一次操作中，你可以执行 $a+=b$，或 $b+=a$。求将 $(a,b)$ 转变为 $(c,d)$ 所需要的最小操作次数，或者如果不可能完成，输出 $-1$。

输入的第一行包含 $Q$。

以下 $Q$ 行，每行包含四个整数 $a$，$b$，$c$，$d$。

每行输出一个查询的答案。

【样例解释】

第一个查询：$(5,-3)\to (2,-3)\to (-1,-3)$。

第二个查询：不可能。

第三个查询：$(5,3)\to (8,3)\to (8,11)\to (8,19)$。

第四个查询：不需要任何操作。

• 测试点 3：$a,b\ge 0$。

• 测试点 4：$a\ge 0\ge b$。

• 测试点 5：$a\le 0\le b$。

• 测试点 6：$a,b\le 0$。

• 测试点 7：$c,d\ge 0$。

• 测试点 8：$c\ge 0\ge d$。

• 测试点 9：$c\le 0\le d$。

• 测试点 10：$c,d\le 0$。

• 测试点 11-14：$Q\le 10^3$。

• 测试点 15-19：没有额外限制。

【数据规模与约定】

• 测试点 2：$|a|,|b|,|c|,|d|\le 10$。

• 测试点 3：$a,b\ge 0$。

• 测试点 4：$a\ge 0\ge b$。

• 测试点 5：$a\le 0\le b$。

• 测试点 6：$a,b\le 0$。

• 测试点 7：$c,d\ge 0$。

• 测试点 8：$c\ge 0\ge d$。

• 测试点 9：$c\le 0\le d$。

• 测试点 10：$c,d\le 0$。

• 测试点 11-14：$Q\le 10^3$。

• 测试点 15-19：没有额外限制。

供题：Benjamin Qi