Success Rate
time limit per test 2 second memory limit per test 256 megabytes
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?

传送门:CF806A

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≤1e9; 0≤p≤q≤1e9; 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.

Sample Input

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

Sample Output

1
2
3
4
4
10
0
-1

题解

问(x+c1)/(y+c1+c2)什么时候等于p/q 比赛时想到二分了,但二分错位置了 首先能变到的肯定都是p/q的倍数,即p×t/q×t 那么可以二分倍数t 满足的情况是 q×t-y>=0&&p×t-x>=0&&q×t-y>=p×t-x 差距是单调的 所以可以二分
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.io.*;  
import java.util.*;
public class Main {
static double eps=1e-12;
public static void main(String[] args) {
FastScanner sc = new FastScanner();
PrintWriter pw = new PrintWriter(System.out);
int n=sc.nextInt();
while (sc.hasNext()) {
long x=sc.nextInt();
long y=sc.nextInt();
long p=sc.nextInt();
long q=sc.nextInt();
if(p==0){
if(x==0){
pw.println(0);
}else{
pw.println(-1);
}
}
else if(p==q){
if(x==y){
pw.println(0);
}else{
pw.println(-1);
}
}else{
long start=0;
long end=(long) 1e9;
long result=end;
while(start<=end){
long mid=(start+end)/2;
if(check(x,y,p*mid,q*mid)){
result=mid;
end=mid-1;
}else{
start=mid+1;
}
}
if(result==end){
pw.println(-1);
}else
pw.println(Math.abs(y-q*result));
}
pw.flush();
}
}
static boolean check(long x,long y,long p,long q){
if(q-y>=0&&p-x>=0&&q-y>=p-x)return true;
else return false;
}
}