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.
//package com.company;
import java.awt.geom.Arc2D;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.nio.BufferUnderflowException;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        InputStream is;
        OutputStream os;
        try {
            is = new FileInputStream("input.txt");
            os = new FileOutputStream("output.txt");
        } catch (FileNotFoundException e) {
            is = System.in;
            os = System.out;
        }
        FastReader in = new FastReader(is);
        PrintWriter out = new PrintWriter(os);
        Solver solver = new Solver(in, out);
        solver.solve();
        out.close();
    }
}

class GcdSol {
    Long x, y;
}

class Solver {
    FastReader in;
    PrintWriter out;

    Long gcdex(Long a, Long b, GcdSol sol)
    {
        if (a == 0)
        {
            sol.x = 0L;
            sol.y = 1L;
            return b;
        }
        GcdSol sol1 = new GcdSol();
        Long g = gcdex(b % a, a, sol1);
        sol.x = sol1.y - (b / a) * sol1.x;
        sol.y = sol1.x;
        return g;
    }

    boolean spec;

    void solve_test(int ix)
    {
        Long x = in.nextLong();
        Long y = in.nextLong();
        Long p = in.nextLong();
        Long q = in.nextLong();
        //if(ix == 0 && x == 1L && y == 1000000000L && p == 1L && q == 1L)
        //    spec = true;
        //if(spec == true && ix == 112)
        //    out.println("x"+x+"y"+y+"p"+p+"q"+q);
        if(x == 0 && y == 0)
        {
            if(p == 0)
                q = 0L;
            out.println(q);
            return;
        }
        if(p == 0)
        {
            if(x == 0)
            {
                out.println(0);
            }
            else
            {
                out.println(-1);
            }
            return;
        }
        if(p.equals(q))
        {
            if(x.equals(y))
            {
                out.println(0);
            }
            else
            {
                out.println(-1);
            }
            return;
        }
        BigInteger dx, dy;
        GcdSol tt = new GcdSol();
        Long g = gcdex(q - p, p, tt);
        tt.y = -tt.y;

        Long a = q - p;
        Long b = p;
        Long c = p * y - x * q;
        if(c == 0)
        {
            out.println(0);
            return;
        }
        dx = new BigInteger(tt.x.toString()).multiply(new BigInteger(c.toString()));
        dy = new BigInteger(tt.y.toString()).multiply(new BigInteger(c.toString()));
        //cout << dx << '*' << a << '-' << dy << '*' << b << '=' << c << '\n';

        if(dx.compareTo(BigInteger.ZERO) < 0)
        {
            //out.println(dx.toString());
            BigInteger k = dx.negate().divide(new BigInteger("" + b));
            if(k.multiply(new BigInteger("" + b)).add(dx).compareTo(BigInteger.ZERO) < 0)
                k = k.add(BigInteger.ONE);
            //out.println(k.toString());
            dx = k.multiply(new BigInteger("" + b)).add(dx);
            dy = k.multiply(new BigInteger("" + a)).add(dy);
            //out.println(dx.toString());
        }
        if(dy.compareTo(BigInteger.ZERO) < 0)
        {
            //out.println(dy.toString());
            BigInteger k = dy.negate().divide(new BigInteger("" + a));
            if(k.multiply(new BigInteger("" + a)).add(dy).compareTo(BigInteger.ZERO) < 0)
                k = k.add(BigInteger.ONE);
            //out.println(a.toString());
            dx = k.multiply(new BigInteger("" + b)).add(dx);
            dy = k.multiply(new BigInteger("" + a)).add(dy);
            //out.println(dy.toString());
        }
        if(dx.compareTo(BigInteger.ZERO) < 0 || dy.compareTo(BigInteger.ZERO) < 0)
        {
            out.println(-1);
            return;
        }
        else
        {
            BigInteger k1 = dx.divide(new BigInteger("" + b));
            BigInteger k2 = dy.divide(new BigInteger("" + a));
            BigInteger k;
            if(k1.compareTo(k2) < 0)
                k = k1;
            else
                k = k2;
            dx = k.multiply(new BigInteger("-" +b)).add(dx);
            dy = k.multiply(new BigInteger("-" + a)).add(dy);
        }
        out.println(dx.add(dy).toString());
    }
    void solve()
    {
        spec = false;
        int ts = in.nextInt();
        for(int i = 0; i < ts; i++)
            solve_test(i);
    }

    public Solver(FastReader in, PrintWriter out)
    {
        this.in = in;
        this.out = out;
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    public FastReader(InputStream is) {
        br = new BufferedReader(new InputStreamReader(is));
        st = null;
    }

    String next() {
        while(st == null || !st.hasMoreTokens())
        {
            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());
    }
}