#1666. 「USACO 2025.2 Silver」Transforming Pairs

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

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

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

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

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

她必须逐次执行这些操作，但可以任意顺序执行任意多次。她必须恰好使第一堆达到 捆，第二堆达到 捆（）。

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

输入的第一行包含 。

以下 行，每行包含四个整数 ，，，。

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

输入 #1

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

输出 #1

-1
3
-1
0

输入 #2

1
1 1 1 1000000000000000000

输出 #2

999999999999999999

样例 1 解释：

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

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

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

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

• 测试点 ：。
• 测试点 ： 且 。
• 测试点 ：没有额外限制。