ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4346: 成功率

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：11 通过：8
提交提交记录统计Web Board

题目描述

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

       您最喜欢的[0;1]范围内的有理数是p/q。现在你想知道：如果你希望你的成功率是p/q，那么你必须提交的最小数量是多少？

You are an experienced Codeforces user. Today you found out that during your activity on Codeforces you have made y submissions, out of which x have been successful. Thus, your current success rate on Codeforces is equal to x/y.
Your favorite rational number in the [0;1] range is p/q. Now you wonder: what is the smallest number of submissions you have to make if you want your success rate to be p/q?
Input
The first line contains a single integer t (1≤t≤1000)− the number of test cases.
Each of the next t lines contains four integers x, y, p and q (0≤x≤y≤109; 0≤p≤q≤109; y>0; q>0).
It is guaranteed that p/q is an irreducible fraction.
Hacks. For hacks, an additional constraint of t≤5 must be met.
Output
For each test case, output a single integer equal to the smallest number of submissions you have to make if you want your success rate to be equal to your favorite rational number, or -1 if this is impossible to achieve.
Example
Input 
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1
Output 
4
10
0
-1
Note
In the first example, you have to make 4 successful submissions. Your success rate will be equal to 7/14, or 1/2.
In the second example, you have to make 2 successful and 8 unsuccessful submissions. Your success rate will be equal to 9/24, or 3/8.
In the third example, there is no need to make any new submissions. Your success rate is already equal to 20/70, or 2/7.
In the fourth example, the only unsuccessful submission breaks your hopes of having the success rate equal to 1.

输入格式

第一行包含单个整数t（1≤t≤1000)，表示测试用例的数量。

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

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

对于黑客，必须满足 t ≤ 5。

输出格式

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

输入样例 复制 

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

输出样例 复制 

4
10
0
-1

数据范围与提示

在第一个示例中，您必须提交4份成功的申请。您的成功率将等于7/14或1/2。
在第二个示例中，您必须提交2个成功的提交和8个不成功的提交。您的成功率将等于9/24或3/8。
在第三个示例中，不需要提交任何新的申请。您的成功率已经等于20/70或2/7。
在第四个示例中，此前已经有一个不成功的提交打破了成功率等于1的希望。

分类标签