You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

聪明奶牛 Bessie 发现了一种新的迷恋——数学魔法！一天，当她在 Farmer John 牧场的草地上小跑时，她偶然发现了两堆有魔法的干草。第一堆包含 $a$ 捆干草，第二堆包含 $b$ 捆干草（$1\le a,b\le 10^{18}$）。

在干草堆边上，半埋在泥土里，她发现了一卷古老的卷轴。当她展开卷轴时，发光的字母揭示了一个预言：

奉大草原之令，被选中者需令此平凡之干草堆转为恰好 $c$ 捆及 $d$ 捆——不可多，亦不可少。

Bessie 意识到她只能施展以下两种魔法：

• 她可以施法召唤新的干草捆以增加第一堆的大小，增加的数量等于当前第二堆的数量。
• 她可以施法召唤新的干草捆以增加第二堆的大小，增加的数量等于当前第一堆的数量。

她必须逐次执行这些操作，但可以任意顺序执行任意多次。她必须恰好使第一堆达到 $c$ 捆，第二堆达到 $d$ 捆（$1\le c,d\le 10^{18}$）。

对于 $T$（$1\le T\le 10^4$）个独立的测试用例中的每一个，输出实现预言所需的最小操作次数，或者如果不可能实现时输出 -1。

输入格式

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

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

输出格式

输出 $T$ 行，为每一个测试用例的答案。

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3

-1
3
-1
0

1
1 1 1 1000000000000000000

999999999999999999

提示

样例 1 解释：

在第一个测试用例中，由于 $b>d$，但操作只可能增加 $b$，因此不可能实现。

在第二个测试用例中，最初两堆有 $(5, 3)$ 捆。Bessie 可以将第一堆增加第二堆的数量，得到 $(8, 3)$ 捆。然后 Bessie 可以将第二堆增加第一堆的新数量，并执行该操作两次，得到 $(8, 11)$ 并最后得到 $(8, 19)$ 捆。这与 $c$ 和 $d$ 一致，且是达到目标的最小操作次数。

注意，第三个测试用例的答案与第二个不同，因为 $c$ 和 $d$ 的值交换了（堆的顺序有影响）。

在第四个测试用例中，不需要任何操作。

• 测试点 $3\sim 4$：$\max(c, d) \le 20 \cdot\min(a, b)$。
• 测试点 $5\sim 7$：$T \le 10$ 且 $a,b,c,d\le 10^6$。
• 测试点 $8\sim 12$：没有额外限制。