题目描述

聪明奶牛 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$：没有额外限制。