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.*;
import java.util.*;
import java.math.*;

public class _412div2Q3
{
    public static void main(String[] args) throws IOException
    {
        FastScanner obj = new FastScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));


		int t = obj.nextInt();
		
		while(t-->0)
		{
			long x = obj.nextLong();
			long y = obj.nextLong();

			long p = obj.nextLong();
			long q = obj.nextLong();

			if(p==0)
			{
				if(x==0)
					out.println(0);
				else
					out.println(-1);
			}
			else if(p==1 && q==1) 
			{
				if(x==y)
					out.println(0);
				else
					out.println(-1);
			}			
			else
			{
				long low = 1;
				long high = (long)1e10;
				long ans = 0l;
				while(high-low>0)
				{
					long mid = (high+low)/2;
					if(((p*mid)-x)>=0 && ((q*mid)-y)>=0 && ((p*mid)-x <= (q*mid)-y))
						high = mid;
					else
					{
						low = mid+1;
						ans = Math.max(mid,ans);
					}
				}
				out.println(Math.max((low*q)-y,(ans*q)-y));
			}
		}
		out.close();		
	}
	
	private static long findGCD(long number1, long number2) 
	{
		if(number2 == 0)
	 		return number1;

		return findGCD(number2, number1%number2); 
	}

	
	
   
 
   //-----------PrintWriter for faster output---------------------------------
   public static PrintWriter out;
      
   //-----------FastScanner class for faster input----------
   public static class FastScanner {
        BufferedReader br;
        StringTokenizer tokenizer;
 
        public FastScanner() throws IOException {
            br = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = new StringTokenizer(br.readLine().trim());
        }
 
        String next() {
            while (tokenizer == null || !tokenizer.hasMoreElements()) {
                try {
                    tokenizer = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                    }
            }
          return tokenizer.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
      
        int[] nextIntArray() throws IOException {
            String[] line = br.readLine().trim().split(" ");
            int[] out = new int[line.length];
            
            for (int i = 0; i < line.length; i++) {
                out[i] = Integer.valueOf(line[i]);
            }
            return out;
        }
        
        BigInteger nextBigInteger() throws IOException {
            return new BigInteger(next());
        }
        
        String nextLine(){
            String str = "";
	        try {
	            str = br.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
        }
 
   }
   //--------------------------------------------------------
} 