聪明奶牛 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$ 行，为每一个测试用例的答案。