← 返回题目列表

AtCoder · agc063_f

F. 同步楼层

中文机器翻译题面 查看原题

分数: 1700 点

问题陈述

给你一对非负整数 a = (a_1,a_2) 和 b = (b_1,b_2)。 您可以对该对执行以下操作 a 任意次数,可能为零。

  • 操作:选择一个 正实数 x。更换 a = (a_1,a_2) 与 (\lfloor a_1x\rfloor, \lfloor a_2x\rfloor).

你的目标是使这对 a 等于该对 b。确定是否可以实现。如果是,请找出为实现该目标而必须执行该操作的最少次数。

你有 T 测试用例解决。

约束

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

输入

输入由标准输入按以下格式给出:

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

每个测试用例均按以下格式给出:

a_1 a_2 b_1 b_2

输出

打印 T 行。的 i- 第行应包含 -1 如果不可能 a 等于 b 在 i-第一个测试用例,否则为实现目标必须执行的操作的最小次数。


示例输入 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
-1
3
-1
4
2
-1

对于第一个测试用例,这是一个最佳解决方案。

  • 最初, a = (2,3).
  • 执行操作 x = 0.6,替换 a 与 (\lfloor 1.2 \rfloor, \lfloor 1.8\rfloor) = (1,1).

对于第三个测试用例,这是一个最佳解决方案。

  • 最初, a = (3,2).
  • 执行操作 x = 1.5,替换 a 与 (4,3).
  • 执行操作 x = 1.7,替换 a 与 (6,5).
  • 执行操作 x = 1.6,替换 a 与 (9,8).

示例输入 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

示例输出 2

0
1
1
2
-1
1
1
-1
0