← 返回题目列表

Codeforces · 773/A

A. 成功率

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

您是一位经验丰富的 Codeforces 用户。今天您发现,在 Codeforces 上的活动期间,您已提交 y 项提交,其中 x 项已成功。因此,您当前在 Codeforces 上的成功率等于 x / y。

[0;1] 范围内您最喜欢的有理数是 p / q。现在你想知道:如果你希望你的成功率达到 p / q,你必须提交的最少数量是多少?

输入

第一行包含一个整数 t (1 ≤ t ≤ 1000) — 测试用例的数量。

接下来的 t 行包含四个整数 x、y、p 和 q (0 ≤ x ≤ y ≤ 109;0 ≤ p ≤ q ≤ 109;y > 0;q > 0)。

保证 p / q 是不可约分数。

黑客。对于黑客攻击,必须满足 t ≤ 5 的附加约束。

输出

对于每个测试用例,如果您希望成功率等于您最喜欢的有理数,则输出一个等于您必须提交的最小提交数量的单个整数;如果不可能实现,则输出 -1。

示例

输入 #1

4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1

输出 #1

4
10
0
-1

注意

在第一个示例中,您必须成功提交 4 次。您的成功率将等于 7 / 14 或 1 / 2。

在第二个示例中,您必须提交 2 次成功和 8 次不成功的提交。您的成功率将等于 9 / 24 或 3 / 8。

在第三个示例中,无需进行任何新的提交。您的成功率已经等于 20 / 70,或 2 / 7。

在第四个示例中,唯一一次不成功的提交打破了您成功率等于 1 的希望。