#667. 数字变换

数字变换

说明

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

题目描述

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

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

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

问:你最少需要操作多少次?如果不可能实现,则输出 -1.

多组数据。

输入格式

第一行:一个整数 TT,表示数据组数。

接下来 TT 行,每行四个整数 aa,bb,cc,dd,描述一组数据。

输出格式

共 TT 行,每组数据的答案占一行。

输入样例

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≤1041 ≤ T ≤ 10^4, 1≤a,b,c,d≤10181 ≤ a, b, c, d ≤ 10^{18}。其中

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