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.math.BigInteger;
import java.util.*;
public class Main {

    public static void main(String[] args) {
	// write your code here
        Scanner dr=new Scanner(System.in);
        int Q;
        Q=dr.nextInt();
        while (Q!=0){
            Q--;
            BigInteger li=new BigInteger("0");
            BigInteger x,y,p,q;
            x=dr.nextBigInteger();y=dr.nextBigInteger();
            p=dr.nextBigInteger();q=dr.nextBigInteger();
            if (p.compareTo(q)==0){
                if (x.compareTo(y)==0)System.out.println("0");
                else System.out.println("-1");
                continue;
            }
            if (p.compareTo(li)==0){
                if(x.compareTo(li)==0)System.out.println("0");
                else System.out.println("-1");
                continue;
            }
            BigInteger yi=new BigInteger("1");
            BigInteger er=new BigInteger("2");
            BigInteger s,l,r,mid;
            s=l=li;r=new BigInteger("1000000000000000000");
            while (l.compareTo(r)<=0){
                mid=l.add(r).divide(er);
                if (q.multiply(x.add(mid)).compareTo(p.multiply(y.add(mid)))>=0){
                    s=mid;r=mid.subtract(yi);
                }else l=mid.add(yi);
            }
            if (q.multiply(x.add(s)).compareTo(p.multiply(y.add(s)))==0)System.out.println(s);
            else{
                x=x.add(s);
                BigInteger z=x.add(p).subtract(yi).divide(p);
                x=z.multiply(p);
                BigInteger ans=x.divide(p).multiply(q).subtract(y);
                y=x.divide(p).multiply(q);
                System.out.println(ans);
            }
        }
    }
}
