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*?
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* ≤ 10<sup class="upper-index">9</sup>; 0 ≤ *p* ≤ *q* ≤ 10<sup class="upper-index">9</sup>; *y* &gt; 0; *q* &gt; 0).

It is guaranteed that *p* / *q* is an irreducible fraction.

Hacks. For hacks, an additional constraint of *t* ≤ 5 must be met.
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.
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1
4
10
0
-1
8
0 1 0 1
0 2 1 2
0 3 1 1
1 2 0 1
1 2 1 1
2 2 0 1
3 3 1 2
4 4 1 1
0
2
-1
-1
-1
-1
3
0
5
1 1000000000 1 2
1 1000000000 1 2
1 1000000000 1 2
1 1000000000 1 2
1 1000000000 1 2
999999998
999999998
999999998
999999998
999999998
5
999999999 1000000000 1 1000000000
999999999 1000000000 1 1000000000
999999999 1000000000 1 1000000000
999999999 1000000000 1 1000000000
999999999 1000000000 1 1000000000
999999998000000000
999999998000000000
999999998000000000
999999998000000000
999999998000000000
5
0 1000000000 999999999 1000000000
0 1000000000 999999999 1000000000
0 1000000000 999999999 1000000000
0 1000000000 999999999 1000000000
0 1000000000 999999999 1000000000
999999999000000000
999999999000000000
999999999000000000
999999999000000000
999999999000000000
1
999999999 1000000000 1 2
999999998
1
50 50 1 1
0
1
100000000 100000000 1 2
100000000
1
3 999999990 1 1000000000
2000000010
5
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1
1 1 1 1
4
10
0
-1
0
5
9999999 10000000 1 1000000000
9999999 10000000 1 1000000000
9999999 10000000 1 1000000000
9999999 10000000 1 1000000000
9999999 10000000 1 1000000000
9999998990000000
9999998990000000
9999998990000000
9999998990000000
9999998990000000
1
0 1000000000 999999999 1000000000
999999999000000000
5
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
999999998000000000
999999998000000000
999999998000000000
999999998000000000
999999998000000000
5
1 1000000000 999999999 1000000000
2 1000000000 999999999 1000000000
3 1000000000 999999999 1000000000
4 1000000000 999999999 1000000000
5 1000000000 999999999 1000000000
999999998000000000
999999997000000000
999999996000000000
999999995000000000
999999994000000000
1
1 1 1 1
0
5
999999997 999999998 2 999999999
999999997 999999998 2 999999999
999999997 999999998 2 999999999
999999997 999999998 2 999999999
999999997 999999998 2 999999999
499999997500000003
499999997500000003
499999997500000003
499999997500000003
499999997500000003
5
1000000000 1000000000 1 1000000000
1000000000 1000000000 1 1000000000
1000000000 1000000000 1 1000000000
1000000000 1000000000 1 1000000000
1000000000 1000000000 1 1000000000
999999999000000000
999999999000000000
999999999000000000
999999999000000000
999999999000000000
5
99999997 999999998 999999998 999999999
99999996 999999997 999999997 999999999
99999997 999999998 999999998 999999999
99999996 999999997 999999997 999999999
99999997 999999998 999999998 999999999
899999999100000001
449999999550000002
899999999100000001
449999999550000002
899999999100000001
1
1000000000 1000000000 1 1000000000
999999999000000000
1
7 7 1 1
0
5
1000000000 1000000000 1 2
1000000000 1000000000 1 2
1000000000 1000000000 1 2
1000000000 1000000000 1 2
1000000000 1000000000 1 2
1000000000
1000000000
1000000000
1000000000
1000000000
1
1000000000 1000000000 1 1
0
1
1 1000000000 999999999 1000000000
999999998000000000
4
1 1000000000 999999999 1000000000
999999999 1000000000 1 1000000000
1 2 0 1
0 1 0 1
999999998000000000
999999998000000000
-1
0
1
1 1000000000 1 2
999999998
5
1 982449707 1 2
1 982449707 1 2
1 982449707 1 2
1 982449707 1 2
1 982449707 1 2
982449705
982449705
982449705
982449705
982449705
5
13 900000007 900000007 900000009
13 900000007 900000007 900000009
13 900000007 900000007 900000009
13 900000007 900000007 900000009
13 900000007 900000007 900000009
405000000449999966
405000000449999966
405000000449999966
405000000449999966
405000000449999966
1
5 10 0 1
-1
1
2 2 1 1
0
5
0 999999999 999999999 1000000000
0 999999999 999999999 1000000000
0 999999999 999999999 1000000000
0 999999999 999999999 1000000000
0 999999999 999999999 1000000000
999999998000000001
999999998000000001
999999998000000001
999999998000000001
999999998000000001
1
0 5 0 1
0
5
999999999 1000000000 1 9999
999999999 1000000000 1 9999
999999999 1000000000 1 9999
999999999 1000000000 1 9999
999999999 1000000000 1 9999
9997999990001
9997999990001
9997999990001
9997999990001
9997999990001
5
999999997 1000000000 3 1000000000
999999997 1000000000 3 1000000000
999999997 1000000000 3 1000000000
999999997 1000000000 3 1000000000
999999997 1000000000 3 1000000000
333333332000000000
333333332000000000
333333332000000000
333333332000000000
333333332000000000
5
1000000000 1000000000 1 1000000000
1000000000 1000000000 1 1000000000
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
999999999000000000
999999999000000000
999999998000000000
999999998000000000
999999998000000000
5
1000000000 1000000000 1 1000000000
1000000000 1000000000 1 1000000000
1000000000 1000000000 1 1000000000
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
999999999000000000
999999999000000000
999999999000000000
999999998000000000
999999998000000000
1
999999998 999999999 1 10
8999999981
5
1 1 1 1
2 2 1 1
100 100 1 1
1000000000 1000000000 1 1
1000000000 1000000000 1 1
0
0
0
0
0
4
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
1 1000000000 999999999 1000000000
999999998000000000
999999998000000000
999999998000000000
999999998000000000
import sys

N = int(input())

for i in range(N):
    x, y, p, q = map(int,input().split())
    y=y-x
    q=q-p
    if q==0:
        print(-1)
    else:
        p1=p
        q1=q
        j=1
        while (x>p1) | (y>q1):
            p1=p1+p
            q1=q1+q
        print(p1+q1-x-y)
