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.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.util.ArrayDeque;
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.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Stack;

//: God does not play dice with the world :)
 public class Main{

     
    
     public static void main(String[] args) throws IOException {
//        String IN = "C:\\Users\\ugochukwu.okeke\\Desktop\\in.file";
//        String OUT = "C:\\Users\\ugochukwu.okeke\\Desktop\\out.file";
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        
           //System.out.println(Long.MAX_VALUE/1000000000);
           int T = Integer.parseInt(br.readLine());
           while(T-->0) {
               String[] in = br.readLine().split(" ");
               int x = Integer.parseInt(in[0]),y = Integer.parseInt(in[1]),p = Integer.parseInt(in[2]),q = Integer.parseInt(in[3]);
               if(p==q) {
                   if(x==y) {
                       bw.append("0\n");
                   }
                   else{
                       bw.append("-1\n");
                   }
               }
               else{
                   long lo = 1;
                   long hi = Long.parseLong("9223372036");
                   long cost1 = x-y;
                   long cost2=q-p;
                   
                   while(lo < hi) {
                       long mid = (1l*lo+1l*hi)/2;
                       long g = 1l*mid*cost2 + cost1;
                       long k = 1l*mid*p-1l*x;
                       long d = 1l*mid*q-1l*y;
                       if(g < 0 || k < 0 || d < 0 ) lo=mid+1;
                       else hi=mid;
                   }
                   long g = 1l*lo*cost2 + cost1;
                   long k = 1l*lo*p-1l*x;
                   long d = 1l*lo*q-1l*y;
                   if(g < 0 || k < 0 || d < 0) bw.append("-1\n");
                   else bw.append((d)+"\n");
               }
           }
        bw.close(); 
     }

    
 }