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.IOException;
import java.io.InputStreamReader;

/**
 * 
 */

/**
 * @author mohanad
 *
 */
public class C {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String nm[]=bf.readLine().split(" ");
		int t=Integer.parseInt(nm[0]);
		StringBuilder out=new StringBuilder();
		
		while (t>0){
			--t;
			nm = bf.readLine().split(" ");
			int x = Integer.parseInt(nm[0]);
			int y = Integer.parseInt(nm[1]);
			int p = Integer.parseInt(nm[2]);
			int q = Integer.parseInt(nm[3]);
			
//			if ((double)(x)/y==(double)(p)/q){
//				out.append("0\n");
//				continue;
//			}
			
			long l=0, h =1000000000, mid , ans=-1;//1000000000
			while (l<=h){
				mid=((l + h) >> 1);
				
				long mp=mid*p,mq=mid*q;
				if ((mp>=x)&&(mq>=y)){
					ans=((mp-x)<=(mq-y))?(mq-y):ans;
					if ((mp-x)<=(mq-y)){
						ans=mq-y;
						h=mid-1;
					}
					else l=mid+1;
				}
				else l=mid+1;
			}
			out.append(ans+"\n");
			
		}
		System.out.println(out);

	}

}
