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 sys


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


def dio_any(a, b, c, w):
    w[2] = gcd(abs(a), abs(b), w)
    if c % w[2] != 0:
        return False
    w[0] *= c / w[2];
    w[1] *= c / w[2];
    if a < 0:
        w[0] *= -1;
    if b < 0:
        w[1] *= -1
    return True


def udiv(x, y):
    return (x + (y - 1)) / y


def balance(x, y, dx, dy):
    # x --> min
    if dx < 0:
        dx = -dx
        dy = -dy

    if x < 0:
        k = udiv(-x, dx)
        x += k * dx
        y += k * dy

    k = x / dx
    x -= k * dx
    y -= k * dy

    # y >= 0
    if y < 0:
        if dy < 0:
            dx = -dx
            dy = -dy
        if dy == 0:
            print -1
            return
        k = udiv(-y, dy)
        x += k * dx
        y += k * dy

    if x < 0:
        print -1
        return

    # y <= x
    if y > x:
        if dx < 0:
            dx = -dx
            dy = -dy
        dd = dx - dy
        if dd <= 0:
            print -1
            return
        k = udiv(y - x, dd)
        x += k * dx
        y += k * dy
        if y < 0:
            print -1
            return
    print x


def diophant(a, b, c):
    w = [0, 0, 0]
    if not dio_any(a, b, c, w):
        print -1
        return
    x = w[0]
    y = w[1]
    dx = b / w[2]
    dy = - a / w[2]
    balance(x, y, dx, dy)


def solver(x, y, p, q):
    a = p
    b = -q
    c = q * x - p * y
    diophant(a, b, c)


def main():
    t = int(raw_input())
    for _ in xrange(t):
        x, y, p, q = map(int, raw_input().strip().split())
        solver(x, y, p, q)


if __name__ == "__main__":
    main()

