题目描述

给定两个非负整数对 $a = (a_1, a_2)$，$b = (b_1, b_2)$。你可以对 $a$ 进行如下操作任意次（也可以不进行操作）：

• 操作：选择一个正实数 $x$，将 $a = (a_1, a_2)$ 替换为 $(\lfloor a_1 x \rfloor, \lfloor a_2 x \rfloor)$。

你的目标是使得 $a$ 和 $b$ 相等。请判断是否有可能达成目标。如果可能，请求出所需操作次数的最小值。

有 $T$ 组测试数据，请分别给出每组的答案。

输入格式

输入通过标准输入给出，格式如下：

$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$

每组测试数据格式如下：

$a_1\ a_2\ b_1\ b_2$

输出格式

请输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。如果无法使 $a$ 等于 $b$，输出 -1；如果可以，请输出所需操作次数的最小值。

样例 1

输入

7
2 3 1 1
1 1 2 3
3 2 9 8
12 34 56 78
56 78 12 34
87 65 43 21
43 21 87 65

输出

1
-1
3
-1
4
2
-1

样例 2

输入

9
5 5 5 5
5 5 3 3
3 9 0 2
3 9 0 3
0 3 3 9
3 0 2 0
5 2 0 0
0 0 5 2
0 0 0 0

输出

0
1
1
2
-1
1
1
-1
0

说明/提示

限制

• $1 \leq T \leq 10^5$
• $0 \leq a_1, a_2, b_1, b_2 \leq 10^9$

样例解释 1

对于第 $1$ 组测试数据，最优方案之一如下：

• 初始时，$a = (2, 3)$。
• 选择 $x = 0.6$ 进行操作，$a$ 变为 $(\lfloor 1.2 \rfloor, \lfloor 1.8 \rfloor) = (1, 1)$。

对于第 $3$ 组测试数据，最优方案之一如下：

• 初始时，$a = (3, 2)$。
• 选择 $x = 1.5$ 进行操作，$a$ 变为 $(4, 3)$。
• 选择 $x = 1.7$ 进行操作，$a$ 变为 $(6, 5)$。
• 选择 $x = 1.6$ 进行操作，$a$ 变为 $(9, 8)$。

由 ChatGPT 4.1 翻译