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.