Success Rate
题意翻译
一共t组数据,每组数据给出4个整数x,y,p,q.现在你一共提交了y次,AC的次数是x次.问你至少要再提交多少次,能让正确率刚好为p/q.如果不可能,输出一行"-1".保证y>0,q>0,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 $ ?
输入输出格式
输入格式
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<=10^{9} $ ; $ 0<=p<=q<=10^{9} $ ; $ 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.
输出格式
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.
输入输出样例
输入样例 #1
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1
输出样例 #1
4
10
0
-1
说明
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.