该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

本题不再额外提供样例文件。

题目描述

给出两个整数 a, b，你可以进行以下操作：

任选其中一个数保持不变，另一个数变成两个数的和。

对于每次得到的两个数，你可以重复执行以上操作，直到第一个数从开始的 a 变成 c，第二个数从开始的 b 变成 d。

问：你最少需要操作多少次？如果不可能实现，则输出 -1.

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行四个整数 $a$，$b$，$c$，$d$，描述一组数据。

输出格式

共 $T$ 行，每组数据的答案占一行。

输入样例

5
1 2 1 2
1 2 2 2
1 3 4 7
1 1 1 12345678987654321
3 5 33582388 318081532024681

输出样例

0
-1
2
12345678987654320
16188154

数据范围

100% 的数据：$1 ≤ T ≤ 10^4$, $1 ≤ a, b, c, d ≤ 10^{18}$。其中

• 有 10% 的数据：$1 ≤ a, b, c, d ≤ 20$
• 另有 15% 的数据：$\max(c, d) ≤ 20 ·min(a, b)$。
• 另有 15% 的数据：$T ≤ 10$ 且 $a,b,c,d ≤ 10^6$。