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

 public class TestClass implements Runnable{
    static ArrayList<Integer>[] al;
         static class Pair implements Comparator<Pair>{
  int a;
  int b;
  Pair(){

  }
  Pair(int a,int b){
    this.a=a;
    this.b=b;
  }
  public int compare(Pair p1,Pair p2){

    return p1.a-p2.a;
 }
}
  
   static InputReader sc = new InputReader(); 
   static long gcd(long a,long b){
    if(a==0){
      return b;
    }
    return gcd(b%a,a);
   }
   static int d;
   static int[] color;
   static boolean[] v;
  /*  static void dfs(int src,int x,int y){
      v[src]=true;
     int  i=1;
     color[src]=x;
      for(int a :al[src]){
        if(v[a]) continue;
        if(i==x|| i==y){
          i++;
          if(i==x|| i==y){
          i++;
        }
        }
        color[a]=i;
        i++;
         
      }
      for(int a:al[src]){
        if(!v[a]){
          dfs(a,color[a],x);
        }
      }




    }*/
    static long[] a;
    static long[] b;
    public static boolean possible(double mid,int n){
      double l=a[1]-b[1]*mid;
      double r=a[1]+b[1]*mid;
      for(int i=2;i<=n;i++){
        l=Math.max(l,a[i]-b[i]*mid);
        r=Math.min(r,a[i]+b[i]*mid);

      }
      if(l>r)return false;
      else  return true;
    }

public static boolean isvowel(char ch){
    if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u'){
        return true;
    }else{
        return false;
    }
}
static long[] fac;
 static long[] inv;
 static long mod=(long)1e9+7;
static int[] prime;
static Integer[] ans;
 
static ArrayList<Integer>[] al1;
static ArrayList<Integer>[] al2;
static int[] lol1;
static int[] lol2;
static boolean[] v1;
static boolean[] v2;
 
 

     public static void main(String args[]) throws IOException
  { 
    new Thread(null, new TestClass(), "whatever", 1<<26).start();
      
           
    }
boolean check(long x,long y,long p,long q,long t){
    return p*t>=x && (q-p)*t>=(y-x);
}
    public void run(){
              int t=i();
              while(t-->0){
                long x=l(); long y=l();
                long p=l(); long q=l();
                long l=-1;
                long r=(long)1e9;
                
                if(!check(x,y,p,q,r)){
                    System.out.println("-1");
                    continue;
                }
                while(r-l>1){
                    long m=(r+l)/2;
                    if(check(x,y,p,q,m)){
                        r=m;
                    }else{
                        l=m;
                    }
                }
                System.out.println(q*r-y);
                
                

              }
              
      }

    
    /////////////////////////////////////////////////////////// shortcuts //////////////////////////////
      public static long modPow(long base, long exp, long mod) {
        base = base % mod;
        long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
                exp--;
            } else {
                base = (base * base) % mod;
                exp = exp >> 1;
            }
 
        }
        return result;
    }
 
 
    public static void cal() {
        fac = new long[1000005];
        inv = new long[1000005];
        fac[0] = 1;
        inv[0] = 1;
        for (int i = 1; i <= 1000000; i++) {
            fac[i] = (fac[i - 1] * i) % mod;
            inv[i] = (inv[i - 1] * modPow(i, mod - 2, mod)) % mod;
        }
    }
 
   /* public static long ncr(int n, int r) {
        return (((fac[n] * inv[r]) % mod) * inv[n - r]) % mod;
    }
 */

      static int i() {
           
          return sc.nextInt();
        }
        static long l()  {
          return sc.nextLong();

        }
        static double d() throws IOException{
          return sc.nextDouble();
        }
        static String s() throws IOException{
          return sc.next();

        }
        static String sL() throws IOException{
          return sc.nextLine();
        }
       static void loop(int[] a) throws IOException{
          for(int j=0;j<a.length;j++){
              a[j]=i();
          }
        }
        static void eloop(int[] a) throws IOException{
          for(int i=1;i<=a.length;i++){
              a[i]=i();
          }
        }
        static void ploop(int[] a)throws IOException{
             for(int j=0;j<a.length;j++){
                System.out.println(a[j]);
             }

        }
        static void eploop(int[] a)throws IOException{
             for(int j=1;j<=a.length;j++){
                System.out.println(a[j]);
             }

        } 
  
        ////////////////////////////////////////////////////////////////////////////////////////////////////
     

   

  static class InputReader {
        BufferedReader br;
        StringTokenizer st;
 
        public InputReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                throw new RuntimeException();
            }
            return str;
        }
    }

 }