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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class SuffixArray {
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	private static long max = Long.MIN_VALUE;
	private static int mod = 1000000000 + 7;
	private static boolean flag=false;
	static int[][] cord;
	private static int block;
	private void soln(){
		int t1=nextInt();
        while(t1-->0)
        {
       	 long x=nextLong();
       	 long y=nextLong();
       	 long p=nextLong();
       	 long q=nextLong();
       	 long low=1;
       	 long high=(long)2e9;
       	 long ans=-1;
       	 while(low<=high)
       	 {
       		 long mid=(low+high)/2;
       		 long x1=mid*p;
       		 long x2=mid*q;
       		 long up=(x1-x);
       		 long down=(x2-y);
       		 if(x1>=x&&x2>=y&&up<=down){
       			 ans=mid;
       			 high=mid-1;
       	    }
       		 else
       			 low=mid+1;
       	 }
       	 if(ans==-1)
       		pw.println(ans);
       	 else
       	 pw.println((ans*q)-y);
        }
	}
	public static void func(int p,int x,int no_hack){
        int start=(x/50)%475;
        int i=0;
        while(i<25){
            start*=96;
            start+=42;
            start%=475;
            if(start+26 == p){
                System.out.println(no_hack);
                System.exit(0);
            }
            i++;
        }
    }
	private static void bfs(int x1,int y1,char[][] arr,int n,int m,int[][] val,int[][] dir){
		//System.out.println(x1+" "+y1);
		if(arr[x1][y1]=='*' || val[x1][y1]>2){
			val[x1][y1]=10;
			return;
		}else{
			if(x1==cord[1][0] && y1==cord[1][1]){
				System.out.println("YES");
				System.exit(0);
			}
			if(dir[x1][y1]==0){
				if(y1!=m-1){
					val[x1][y1+1]=val[x1][y1];
					dir[x1][y1+1]=dir[x1][y1];
					bfs(x1,y1+1,arr,n,m,val,dir);
				}
				if(val[x1][y1]!=2){
				if(x1!=0){
					dir[x1-1][y1]=2;
					val[x1-1][y1]=val[x1][y1]+1;
					bfs(x1-1,y1,arr,n,m,val,dir);
				}
				if(x1!=n-1){
					dir[x1+1][y1]=3;
					val[x1+1][y1]=val[x1][y1]+1;
					bfs(x1+1,y1,arr,n,m,val,dir);
				}}
			}else if(dir[x1][y1]==1){
				if(y1!=0){
					val[x1][y1-1]=val[x1][y1];
					dir[x1][y1-1]=dir[x1][y1];
					bfs(x1,y1-1,arr,n,m,val,dir);
				}
				if(val[x1][y1]!=2){
				if(x1!=0){
					dir[x1-1][y1]=2;
					val[x1-1][y1]=val[x1][y1]+1;
					bfs(x1-1,y1,arr,n,m,val,dir);
				}
				if(x1!=n-1){
					dir[x1+1][y1]=3;
					val[x1+1][y1]=val[x1][y1]+1;
					bfs(x1+1,y1,arr,n,m,val,dir);
				}}
			}else if(dir[x1][y1]==2){
				if(x1!=0){
					val[x1-1][y1]=val[x1][y1];
					dir[x1-1][y1]=dir[x1][y1];
					bfs(x1-1,y1,arr,n,m,val,dir);
				}
				if(val[x1][y1]!=2){
				if(y1!=0){
					dir[x1][y1-1]=1;
					val[x1][y1-1]=val[x1][y1]+1;
					bfs(x1,y1-1,arr,n,m,val,dir);
				}
				if(y1!=m-1){
					dir[x1][y1+1]=0;
					val[x1][y1+1]=val[x1][y1]+1;
					bfs(x1,y1+1,arr,n,m,val,dir);
				}}
			}else{
				if(x1!=n-1){
					val[x1+1][y1]=val[x1][y1];
					dir[x1+1][y1]=dir[x1][y1];
					bfs(x1+1,y1,arr,n,m,val,dir);
				}
				if(val[x1][y1]!=2){
				if(y1!=0){
					dir[x1][y1-1]=1;
					val[x1][y1-1]=val[x1][y1]+1;
					bfs(x1,y1-1,arr,n,m,val,dir);
				}
				if(y1!=m-1){
					dir[x1][y1+1]=0;
					val[x1][y1+1]=val[x1][y1]+1;
					bfs(x1,y1+1,arr,n,m,val,dir);
				}}
			}
		}
	}
	static class Suffix implements Comparable<Suffix>{
		int index;
		String s;
		@Override
		public int compareTo(Suffix arg0){
			return s.charAt(index)-s.charAt(arg0.index);
		}	
	}
	private static Integer[] buildSuffix(String s,int n){
		Integer[] SA=new Integer[n];
		int[] iSA=new int[n];
		Suffix[] arr=new Suffix[n];
		for(int i=0;i<n;i++)
			SA[i]=i;
		Arrays.sort(SA,new Comparator<Integer>(){
			@Override
			public int compare(Integer arg0, Integer arg1) {
				return s.charAt(arg0)-s.charAt(arg1);
			}
		});
		boolean[] bh=new boolean[n];
		boolean[] b2h=new boolean[n];
		for (int i=0;i<n;++i){
		    bh[i] = (i==0) || s.charAt(SA[i])!=s.charAt(SA[i-1]);
		    b2h[i]=false;
		}
		int[] next=new int[n];
		int[] cnt=new int[n];
		for(int k=1;k<n;k<<=1){
			int bucket=0;
			for(int i=0,j;i<n;i=j){
				j=i+1;
				while(j<n && !bh[j]) j++;
				next[i]=j;
				bucket++;
	        }
			if(bucket==n)
				break;
			for(int i=0;i<n;i=next[i]){
				cnt[i]=0;
				for(int j=i;j<next[i];j++)
					iSA[SA[j]]=i;
			}
			cnt[iSA[n-k]]++;
			b2h[iSA[n-k]]=true;
			for(int i=0;i<n;i=next[i]){
				for(int j=i;j<next[i];++j){
			        int s1 = SA[j]-k;
			        if (s1>=0){
			        	int head=iSA[s1];
			        	iSA[s1]=head+(cnt[head]++);
			        	b2h[iSA[s1]] = true;
			        }
				}
			    for(int j=i;j<next[i];++j){
			        int s1=SA[j]-k;
			        if (s1>=0 && b2h[iSA[s1]]){
			        	for(int k1=(iSA[s1]+1); k1<n && !bh[k1] && b2h[k1];k1++)
			        		b2h[k1]=false;
			        }
			    }
			}
			for (int i=0; i<n; ++i){
				SA[iSA[i]]=i;
			    bh[i] |= b2h[i];
			}
		}
		for (int i=0;i<n;++i){
			iSA[SA[i]] = i;
		}
		return SA;
	}
	private int[] lcpArray(Integer[] SA,int n,String s){
		int[] iSA=new int[n];
		int[] lcp=new int[n];
		for(int i=0;i<n;i++)
			iSA[SA[i]]=i;
		lcp[0]=0;
		for(int i=0,j=0;i<n;i++){
			if(iSA[i]>0){
				int k=SA[iSA[i]-1];
				while(i+j<n && k+j<n && s.charAt(i+j)==s.charAt(j+k))
					j++;
				lcp[iSA[i]]=j;
				if(j>0)
					j--;
			}
		}
		return lcp;
	}
	public class Merge{
		public void sort(int inputArr[]) {
	        int length = inputArr.length;
	        doMergeSort(inputArr,0, length - 1);
	    }
	    private void doMergeSort(int[] arr,int lowerIndex, int higherIndex) {         
	        if (lowerIndex < higherIndex) {
	            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
	            doMergeSort(arr,lowerIndex, middle);
	            doMergeSort(arr,middle + 1, higherIndex);
	            mergeParts(arr,lowerIndex, middle, higherIndex);
	        }
	    }
	    private void mergeParts(int[]array,int lowerIndex, int middle, int higherIndex) {
	    	int[] temp=new int[higherIndex-lowerIndex+1];
	        for (int i = lowerIndex; i <= higherIndex; i++) {
	            temp[i-lowerIndex] = array[i];
	        }
	        int i = lowerIndex;
	        int j = middle + 1;
	        int k = lowerIndex;
	        while (i <= middle && j <= higherIndex) {
	            if (temp[i-lowerIndex] < temp[j-lowerIndex]) {
	                array[k] = temp[i-lowerIndex];
	                i++;
	            } else {
	                array[k] = temp[j-lowerIndex];
	                j++;
	                //cnt+=(middle+1-i);
	            }
	            k++;
	        }
	        while (i <= middle) {
	            array[k] = temp[i-lowerIndex];
	            k++;
	            i++;
	        }
	        while(j<=higherIndex){
	        	array[k]=temp[j-lowerIndex];
	        	k++;
	        	j++;
	        }
	    }
	}
	private long pow(long a, long b, long c) {
		if (b == 0)
			return 1;
		long p = pow(a, b / 2, c);
		p = (p * p) % c;
		return (b % 2 == 0) ? p : (a * p) % c;
	}
	private class Pair{
		int x;
		int y;
		public Pair(int a,int b) {
			x=a;y=b;
		}
	}
	private int gcd(int a1, int a2) {
		if (a2 == 0)
			return a1;
		return gcd(a2, a1 % a2);
	}
	public static void main(String[] args) throws Exception {
		InputReader(System.in);
		pw = new PrintWriter(System.out);
		new SuffixArray().soln();
		pw.close();
	}
	public static void InputReader(InputStream stream1) {
		stream = stream1;
	}
	private boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
	private int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}
	private int nextInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	private long nextLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	private String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}
	private String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}
	private int[] nextIntArray(int n) {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextInt();
		}
		return arr;
	}
	private long[] nextLongArray(int n) {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextLong();
		}
		return arr;
	}
	private void pArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}
	private void pArray(long[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}
	private boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}
	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}