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.InputStreamReader;
import java.io.Reader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class cfs412C {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			BigInteger X = new BigInteger(sc.next());
			BigInteger Y = new BigInteger(sc.next());
			BigInteger P = new BigInteger(sc.next());
			BigInteger Q = new BigInteger(sc.next());
			if ( P.equals(Q) && Q.equals(BigInteger.ONE)) {
				if (!X.equals(Y)) {
					System.out.println(-1);
				} else if (X.equals(Y) && X.equals(BigInteger.ZERO)) {
					System.out.println(1);
				} else {
					System.out.println(0);
				}
				continue;
			}
			if (P.equals(BigInteger.ZERO)&& !X.equals(BigInteger.ZERO)) {
				System.out.println(-1);
				continue;
			}
			BigInteger t0 = ((Y.mod(Q)).negate().add(Q)).mod(Q);
			if (works(t0, X, Y, P, Q)) {
				System.out.println(t0);
				continue;
			}
			BigInteger two = new BigInteger("2");
			BigInteger d = BigInteger.ONE;
			while (!works(t0.add(d.multiply(Q)), X, Y, P, Q)) {
				d = d.multiply(two);
				/*if (d.compareTo(BigInteger.ZERO) <= 0) {
					d = Long.MAX_VALUE / 4;
					break;
				}*/
			}
			BigInteger low = new BigInteger("1");
			BigInteger high = d;
			for (int i = 0; i < 60 ; i++) {
				BigInteger mid = (low.add(high)).shiftRight(1);
				if (works (t0.add(mid.multiply(Q)), X, Y, P, Q)) {
					high = mid;
				} else {
					low = mid;
				}
			}
			BigInteger ans = works(t0.add(low.multiply(Q)), X, Y, P, Q) ? t0.add(low.multiply(Q)) : t0.add(high.multiply(Q));
			System.out.println(ans);
		}

	}
	
	public static boolean works (BigInteger t, BigInteger x, BigInteger y, BigInteger p, BigInteger q) {
		BigInteger k = ((p.multiply((y.add(t))).divide(q)).subtract(x));
		return k.compareTo(t) <= 0 && k.compareTo(BigInteger.ZERO) >= 0;
	}
	
	
	public static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(Reader in) {
			br = new BufferedReader(in);
		}

		public FastScanner() {
			this(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String readNextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

		int[] readIntArray(int n) {
			int[] a = new int[n];
			for (int idx = 0; idx < n; idx++) {
				a[idx] = nextInt();
			}
			return a;
		}

		long[] readLongArray(int n) {
			long[] a = new long[n];
			for (int idx = 0; idx < n; idx++) {
				a[idx] = nextLong();
			}
			return a;
		}
	}

}
