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.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Div2_412C {
	public static void main(String args[]) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		int n = in.nextInt();
		Solver solver = new Solver();
		solver.solve(n, in, out);
		out.close();
	}
	
	static class Solver {
		public void solve(int textNum, InputReader in, PrintWriter out) {
			for (int k = 0; k < textNum; k++) {
				long a = in.nextInt();
				long b = in.nextInt();
				long p = in.nextInt();
				long q = in.nextInt();
				long count = 0;
				if (p == q) {
					if (a != b) {
						out.println(-1);
					} else {
						out.println(0);
					}
				} else if (p == 0) {
					if (a == 0) {
						out.println(0);
					} else {
						out.println(-1);
					}
				} else {
					if (a == 0) {
						a += 1;
						b += 1;
						count += 1;
					}
					if (a % p != 0) {
						count += (p - a % p);
						b += (p - a % p);
						a += (p - a % p);
					}
					if (b > a / p * q) {
						long r = b - (a / p) * q;
						//System.out.println(r);
						long temp = (long)Math.ceil(((double)r) / ((double)(q - p))) * p;
						//System.out.println("1 " + a);
						//System.out.println("2 " + b);
						//System.out.println(temp);
						a += temp;
						b += temp;
						count += temp;
						//System.out.println(count);
						//System.out.println("b " + b);
						//System.out.println("a " + (a / p * q - b));
					}
					count += (a / p * q - b);
					//System.out.println(count);
					out.println(count);
				}
			}
		} 
	}
	
	static class InputReader {
		BufferedReader reader;
		StringTokenizer tokenizer;
		
		InputReader(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreElements()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}
