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 ≤ 10^9; 0 ≤ p ≤ q ≤ 10^9; 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.

Difficulty: interview

Starter code:

Solutions:
def solve(x, y, p, q):
    if p == 0: return 0 if x == 0 else -1
    pp = (x - 1) // p + 1 if p != 0 else 0
    L = max((y - 1) // q + 1, pp) - 1
    L = max(L, -1)
    z = y - x
    INF = L + 10 ** 10
    R = INF
    while R - L > 1:
        M = (L + R) >> 1
        cur = q * M
        curp = p * M
        curz = cur - curp
        dl = cur - y
        if curp >= x and curz >= z:
            R = M
        else:
            L = M
        #print(L, R)
    if R == INF:
        return -1
    return R * q - y

read = lambda: map(int, input().split())
t = int(input())
for i in range(t):
    x, y, p, q = read()
    print(solve(x, y, p, q))

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

class solution:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

def eu (a, b, sol):
    if a == 0:
        sol.x = 0
        sol.y = 1
        return b
    sol2 = solution()
    d = eu (b%a, a, sol2)
    sol.x = sol2.y - (b // a) * sol2.x
    sol.y = sol2.x
    return d


def find_any_solution (a, b, c, sol):
    g = eu(abs(a), abs(b), sol)
    if c % g != 0:
        return -1
    sol.x *= c // g
    sol.y *= c // g
    if (a < 0):
        sol.x *= -1
    if (b < 0):
        sol.y *= -1
    return g


def shift_solution (sol, a, b, cnt):
    sol.x += cnt * b
    sol.y -= cnt * a


def find_all_solution(a, b, c, minx, maxx, miny, maxy):
    sol = solution()
    g = find_any_solution(a, b, c, sol)
    if g == -1:
        return (-1, -1)

    a //= g
    b //= g

    sign_a = 1
    if a < 0:
        sign_a = -1
    sign_b = 1
    if b < 0:
        sign_b = -1

    shift_solution(sol, a, b, (minx - sol.x) // b)
    if sol.x < minx:
        shift_solution (sol, a, b, sign_b)
    if sol.x > maxx:
        return (-1, -1)
    lx1 = sol.x

    shift_solution (sol, a, b, (maxx - sol.x) // b)
    if sol.x > maxx:
        shift_solution (sol, a, b, -sign_b)
    rx1 = sol.x

    shift_solution (sol, a, b, - (miny - sol.y) // a)
    if sol.y < miny:
        shift_solution (sol, a, b, -sign_a)
    if sol.y > maxy:
        return (-1, -1)
    lx2 = sol.x

    shift_solution (sol, a, b, - (maxy - sol.y) // a)
    if sol.y > maxy:
        shift_solution (sol, a, b, sign_a)
    rx2 = sol.x

    if lx2 > rx2:
        lx2, rx2 = rx2, lx2
    lx = max (lx1, lx2)
    rx = min (rx1, rx2)

    if lx > rx:
        return (-1, -1)
    return (lx, rx)

def solve():
    s = input().split()
    x = int(s[0])
    y = int(s[1])
    p = int(s[2])
    q = int(s[3])

    # x, y, p, q = 3, 10, 1, 2
 
    if p == 0:
        if x == 0:
            return 0
        else:
            return -1
    if q == p:
        if x == y:
            return 0
        return -1
    if p * y - q * x == 0:
        return 0

    a = q - p
    b = -p
    c = p * y - q * x

    ans1, ans2 = find_all_solution(a, b, c, 0, int(10 ** 20), 0, int(10 ** 20))

    ansy1 = (p * y - q * x - (q - p) * ans1) // (-p)
    ansy2 = (p * y - q * x - (q - p) * ans2) // (-p)

    # print(x, y)

    sum1 = int(10 ** 25)
    if ans1 >= 0 and ansy1 >= 0 and (x + ans1) * q == (y + ansy1 + ans1) * p:
        sum1 = min(sum1, ans1 + ansy1)

    if ans2 >= 0 and ansy2 >= 0 and (x + ans2) * q == (y + ansy2 + ans2) * p:
        sum1 = min(sum1, ans2 + ansy2)
    if sum1 == int(10 ** 25):
        return -1
    return sum1
# print(solve())

t = int(input())
for i in range(t):
    print(solve())

t = int(input())
for i in range(t):
    x, y, p, q = map(int, input().split())
    
    if p == q:
        if x != y:
            print(-1)
        else:
            if x == y == 0:
                print(1)
            else:
                print(0)
        continue
    if p == 0:
        if x == 0:
            if y == 0:
                print(1)
            else:
                print(0)
        else:
            print(-1)
        continue
    
    k = max((y - x + q - p - 1) // (q - p), (x + p - 1) // p) 
    print(k * q - y)

def gcd(a, b):
	if a == 0:
		return [b, 0, 1]
	d = gcd(b % a, a)
	return [d[0], d[2] - (b // a) * d[1], d[1]]

t = int(input())
while t > 0:
	t -= 1
	x, y, p, q = list(map(int, input().split()))
	if p == q:
		if x == y:
			print(0)
		else:
			print(-1)
		continue
	if p == 0:
		if x == 0:
			print(0)
		else:
			print(-1)
		continue
	a = p - q
	b = p
	c = q * x - p * y
	g, xa, ya = gcd(abs(a), abs(b))
	if c % g != 0:
		print(-1)
	else:
		xa *= c // g
		ya *= c // g
		if a < 0:
			xa = -xa
		if b < 0:
			ya = -ya
		if xa < 0:
			gaps = (-xa + (b // g) - 1) // (b // g)
			xa += gaps * (b // g)
			ya -= gaps * (a // g)
		if ya < 0:
			gaps = (-ya + (-a // g) - 1) // (-a // g)		
			xa += gaps * (b // g)
			ya -= gaps * (a // g)
		#print(xa, ya, a, b, c)
		if xa < 0 or ya < 0:
			print(-1)
		else:
			addon = min(xa // (b // g), ya // (-a // g))
			xa -= addon * (b // g)
			ya += addon * (a // g)
			print(xa + ya)


import sys
def de(x, y):
	if (x % y == 0):
		 return x // y
	return x // y + 1

def euc(a, b):
	if (b == 0):
		return 1, 0
	x, y = euc(b, a % b)
	return -y, -x - y * (a // b)



def solve( x, y, p, q):
	if (q == p):
		if (x == y):
			 return 0
		return -1
	if (p == 0):
		if (x == 0):
			 return 0
		return -1
	
		
	a0, b0 = euc(p, q)
	g = a0 * p - q * b0
	c = x * q - p * y
	if (c % g):
		return -1
	a0 = a0 * (c // g)
	b0 = b0 * (c // g)
	t1 = a0 // q
	
	t = max(de(b0 - a0, q - p), de(-b0, p))
	a = a0 + q * t
	b = b0 + p * t

	return a


#sys.stdin = open('input.txt', 'r')


t = int(input())
for it in range(t):
	x, y, p, q = list(map(int, input().split()))
	print(solve(x, y, p, q))


def xgcd(a, b):
    if b == 0:
        return 1, 0
    x1, y1 = xgcd(b, a % b)
    return y1, x1 - (a // b) * y1

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

t = int(input())
for kek in range(t):
    x, y, p, q = map(int, input().split())
    if p == 0:
        if x == 0:
            print(0)
        else:
            print(-1)
        continue
    if p == q:
        if x == y:
            print(0)
        else:
            print(-1)
        continue

    v = p * y - q * x
    g = gcd(q - p, p)
    k0, l0 = xgcd(q - p, p)
    l0 *= -1
    g1 = v // g
    k0 *= g1
    l0 *= g1

    xx = (-k0 + p - 1) // p
    
    xx = max(xx, (-l0 + q - p - 1) // (q - p))
    
    l = l0 + xx * (q - p)
    k = k0 + xx * p;

    print(k + l)

def gcd(a, b):
    if a == 0:
        return b, 0, 1

    g, x1, y1 = gcd(b % a, a);

    y = x1;
    x = y1 - (b // a) * x1;
    return g, x, y;

def comp(da, db, t, a, b):
    ra = a + da * t
    rb = b + db * t

    # assert(ra.v0 >= 0);
    # assert(ra.v1 >= 0);
    # assert(rb.v0 >= 0);
    # assert(rb.v1 >= 0);
    return ra + rb

def solve():
    x, y, p, q = list(map(int, input().split()))

    if p == q:
        if x == y:
            print(0)
        else:
            print(-1)
        return

    if p == 0:
        if x == 0:
            print(0)
        else:
            print(-1)
        return;

    r = x * q - y * p;
    g, a, b = gcd(p - q, p);
    if r % g != 0:
        print(-1)
        return

    a *= r // g;
    b *= r // g;

    da = p;
    db = q - p;
    minT = -10**18;
    minT = max(minT, ((-a + (da - 1)) // da));
    minT = max(minT, ((-b + (db - 1)) // db));

    t = minT;
    rr = comp(da, db, t, a, b);
    print(rr)


def main():
    t = int(input())
    for i in range(t):
        solve()

def __starting_point():
    main()


__starting_point()

def gcd(a, b):
	if (a == 0):
		return (b, 0, 1)

	(g, x, y) = gcd(b % a, a)
	return (g, y - (b // a) * x, x) 


t = int(input())

for i in range(t):
	(x, y, p, q) = list(map(int, input().split()))
	val = p * y - q * x
	(g, a, b) = gcd(q, -p)

	if (val % g != 0):
		print(-1)
		continue

	a *= val // g
	b *= val // g

	da = abs(p // g)
	db = abs(q // g)

	if (a < 0):
		if (da == 0):
			print(-1)
			continue

		mul = (abs(a) + da - 1) // da
		a += mul * da
		b += mul * db


	if (b < 0):
		if (db == 0):
			print(-1)
			continue

		mul = (abs(b) + db - 1) // db;
		a += mul * da
		b += mul * db

	if (a > b):
		if (da == db):
			print(-1)
			continue

		diff = a - b
		step = db - da
		mul = (diff + step - 1) // step
		a += mul * da
		b += mul * db

	mul = b // db;
	if (da != 0):
		mul = min(mul, a // da)

	if (da != db):
		mul = min(mul, (b - a) // (db - da))

	print(b - db * mul) 


INF = 10**40

def gcd_ex(A, B):
    if A == 0:
        return B, 0, 1
    g, a1, b1 = gcd_ex(B % A, A)
    a = b1 - (B // A) * a1
    b = a1
    return g, a, b

def round_down(a, b):
    s = (a < 0) != (b < 0)
    a = abs(a)
    b = abs(b)
    if not s:
        return a // b
    return -((a + b - 1) // b)

def round_up(a, b):
    s = (a < 0) != (b < 0)
    a = abs(a)
    b = abs(b)
    if not s:
        return (a + b - 1) // b
    return -(a // b)

def solve():
    x, y, p, q = list(map(int, input().split()))

    A = q
    B = -p
    C = p * y - q * x

    g, a0, b0 = gcd_ex(A, -B)
    b0 *= -1

    if C % g != 0:
        print(-1)
        return
    a0 *= C // g
    b0 *= C // g

    k_up1 = 0
    if B == 0:
        if -a0 > 0:
            print(-1)
            return
        k_up1 = INF
    else:
        k_up1 = round_down(-a0, B // g)

    k_down2 = 0
    k_up2 = 0
    if A + B == 0:
        if b0 - a0 < 0:
            print(-1)
            return
        k_down2 = -INF
        k_up2 = INF
    elif A + B > 0:
        k_down2 = -INF
        k_up2 = round_down(b0 - a0, (A + B) // g)
    else:
        k_down2 = round_up(b0 - a0, (A + B) // g)
        k_up2 = INF

    k_down = k_down2
    k_up = min(k_up1, k_up2)
    if k_down > k_up:
        print(-1)
        return

    if k_up == INF:
        raise Exception
    b = b0 - (A // g) * k_up

    print(b)

def main():
    t = int(input())
    for i in range(t):
        solve()

main()


t = int(input())

for i in range(t):
    x, y, p, q = [int(i) for i in input().split()]
    
    if p == 0:
        if x == 0:
            print(0)
        else:
            print(-1)
        continue

    l = 0
    r = 10000000000

    while l < r:
        t = (l + r) // 2

        c1 = p * t - x
        c2 = q * t - y - c1

        if c1 >= 0 and c2 >= 0:
            r = t
        else:
            l = t + 1

    if r == 10000000000:
        print(-1)
    else:
        print(q * l - y)


def gcd(a, b):
    if b > a:
        return gcd(b, a)
    if b == 0:
        return a
    return gcd(b, a % b)

def works(a, b, c, d, x):
    return b <= d * x and a <= c * x and d * x - b >= c * x - a

def solve():
    a, b, c, d = list(map(int, input().rstrip().split()))
    if c == d == 1 and not a / b == 1:
        print(-1)
        return
    if c == 0 and not a == 0:
        print(-1)
        return
    g = gcd(c, d)
    c //= g
    d //= g
    low = -1
    high = 1000000000000
    while low + 1 < high:
        mid = (low + high) // 2
        if works(a, b, c, d, mid):
            high = mid
        else:
            low = mid
    print(d * high - b)

def __starting_point():
    t = int(input())
    for _ in range(t):
        solve()

__starting_point()

# cook your code here
def solve():
    x, y, p, q = map(int, input().split())
    
    if p == 0:
        if x == 0:
            print(0)
            return
        else:
            print(-1)
            return
        
    if p == q:
        if x == y:
            print(0)
            return
        else:
            print(-1)
            return
        
    var1 = ( p + x - 1 ) // p;
    var2 = ((y - x) + (q - p) - 1) // (q - p);
    max1 = max(var1, var2);
    solution = (max1 * q) - y;
    
    print(solution)
    return


def main():
    n = int(input())
    for i in range (n):
        solve()
        
main()

for i in range(int(input())):
    x, y, p, q = map(int, input().split())
    print(-(x > 0) if not p else -(y > x) if p == q else max((x - 1) // p, (y - x - 1) // (q - p)) * q + q - y)

import math
import sys
t=int(input())
for j in range(1,(t+1)):
    x,y,p,q=(list(map(int,input().split())))
    f1=0
    if(p!=q and p!=0):
            tmp=max(((y-x)+(q-p)-1)//(q-p),(x+p-1)//p)
            #print(tmp)
            #include<FU*k> test case
            print((q*tmp)-y)
            f1=1
           
    if(p==0 and x==0):
            print(0)
    elif(p==q and x==y):
            print(0)
    elif (not f1):
            print(-1)
        
        


    


for case in range(int(input())):
    x,y,p,q = map(int, input().split())

    lo = 0
    hi = 10**10
    while lo < hi:
        mid = lo + (hi - lo) // 2
         
        np,nq = mid*p, mid*q
        if nq >= y and np >= x:
            if nq - y >= np - x:
                hi = mid
            else:
                lo = mid + 1
        else:
            lo = mid + 1
     
    print(lo * q - y if lo != 10**10 else -1)

for _ in range(int(input())):

  x,y,p,q=list(map(int,input().split()))

  l,r,res=0,10**18,-1

  while l<=r:

    mid=(l+r)//2

    a,b=p*mid-x,q*mid-y

    if a<=b and a>-1 and b>-1:res=b;r=mid-1

    else :l=mid+1

  print(res)



# Made By Mostafa_Khaled


R = lambda: map(int, input().split())
mx = 10**9 + 7
t = int(input())
for i in range(t):
    a, b, p, q = R()
    l, r = 1, mx
    while l < r:
        k = (l + r) // 2
        x, y = k * p - a, k * q - b
        if 0 <= x <= y and y >= 0:
            r = k
        else:
            l = k + 1
    if r >= mx:
        print("-1")
    else:
        print(r * q - b)

N = int(input())
import math
for _ in range(N):
    x,y,p,q = [int(x) for x in input().split()]
    if (p == 0) or (p==q):
        if (x*q == p*y):
            print(0)
        else:
            print(-1)
        continue
    n = math.ceil((y-x)/(q-p))
    n = max(n,math.ceil(x/p))
    n = max(n,math.ceil(y/q))
    print(n*q-y)


import math
for _ in range(int(input())):
    x,y,p,q = [int(x) for x in input().split()]
    print(math.ceil(max((y-x)/(q-p),x/p,y/q))*q-y) if p%q else print(0) if (x*q == p*y) else print(-1)


#https://codeforces.com/problemset/problem/773/A

t = int(input())
for i in range(t):
    x, y, p, q = list(map(int, input().split()))
    left = -1
    right = 10**9
    r = right
    while left + 1 < right:
        t = (left + right) // 2
        if p*t >= x and q*t - p*t >= y - x:
            right = t
        else:
            left = t
    if not (p*r >= x and q*r - p*r >= y - x):
        print(-1)
    else:
        print(q*right - y)
    


from math import ceil
for _ in range(int(input())):
    x, y, p, q = list(map(int, input().split()))
    if p == q and x != y:
        print(-1)
    elif p == q:
        print(0)
    elif p == 0 and x == 0:
        print(0)
    elif p == 0:
        print(-1)
    else:
        a = y // q
        r = y % q
        g1 = (x - p * a + p - 1) // p
        g2 = ceil((x - r - p * a) / (p - q))
        print(max(g1, g2) * q - r)


import math
for _ in range(int(input())):
    x, y, p, q = list(map(int,input().split()))
    if p == 0 or  p == q :
        print(0 if  x * q == p * y else  -1 )
        continue    
    n = math.ceil((y - x) / (q - p) )
    n = max(n, math.ceil(x / p))
    n = max(n, math.ceil(y / q))
    print(n * q - y )


T = int(input())

for t in range(T):
  x, y, p, q = map(int, input().split())
  if p == q and x != y:
      print(-1)
      continue

  INF = 10000000000
  lb = -1
  ub = INF
  mod_y = (q - y % q) % q

  while ub - lb > 1:
    mid = (ub + lb) // 2
    diff = mod_y + q * mid
    bunbo = y + diff
    bunshi = p * bunbo // q
    if bunshi >= x and bunshi - x <= diff:
      ub = mid
    else:
      lb = mid
  if ub == INF:
    print(-1)
  else:
    print(mod_y + q * ub)

def chec(a,b,p,q,mid):
    if p*r>=a and (q-p)*mid>=b-a:
        return True
    else:
        return False
def check(np, nq):
  return np >= a and nq >= b and (np - a <= nq - b)    
for _ in range(int(input())):
    a,b,p,q = list(map(int,input().split()))
    l=0
    r=10000000000
    if check(p*r,q*r)==False:
        print(-1)
        continue
    while l<=r:
        mid = l +(r-l)//2
        if check(p*mid,q*mid):
            r=mid-1
        else:
            l=mid+1
    print(l*q-b)


def div(a, b):
	return (a+b-1)//b

for t in range(int(input())):
	x,y,p,q = map(int,input().split())
	if q == 1:
		if p == 0 and x == 0 or p == 1 and x == y:
			print(0)
		else:
			print(-1)
	else:
		z = max(max(div(x,p),div(y,q)),max(div(y-x,q-p),0))
		print(z*q-y)