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.
def gcd(a, b):
	if a == 0:
		return [b, 0, 1]
	d, x1, y1 = gcd (b % a, a)
	return [d, y1 - (b // a) * x1, x1]
def find_any_solution(a, b, c):
	g, x0, y0 = gcd(abs(a), abs(b))
	if c % g != 0:
		return [False, 0, 0, 0]
	x0 *= c // g
	y0 *= c // g
	if a < 0:
		x0 *= -1
	if b < 0:
		y0 *= -1
	return [True, x0, y0, g]
def main():
	x, y, p, q = [int(i) for i in input().split()]
	if p == 0 and x != 0:
		print(-1)
		return 0
	ok = find_any_solution(q, -p, p * y - x * q);
	if not ok[0]:
		print(-1)
		return;
	#print(ok)
	a = ok[1]
	b = ok[2]
	g = ok[3]
	ag = q // g
	bg = (-p) // g; 
	#print(a, b, ag, bg)
	if ag == -1 * bg and a > b:
		print(-1)
		return 0
	l, r = -10 ** 18, 10 ** 18
	while r - l > 1:
		m = (l + r) // 2;
		if a + m * bg >= 0:
			l = m
		else:
			r = m
	maxk = l
	l, r = -10 ** 18, 10 ** 18
	while r - l > 1:
		m = (l + r) // 2;
		if b - m * ag >= 0:
			l = m
		else:
			r = m
	maxk = min(maxk, l)
	l, r = -10 ** 18, 10 ** 18
	while r - l > 1:
		m = (l + r) // 2
		if a + m * bg <= b - m * ag:
			l = m
		else:
			r = m
	if ag != bg * -1:
		maxk = min(l, maxk)
	if b - maxk * ag + y == 0:
		--maxk
	if b - maxk * ag + y == 0:
		print(-1)
		return;
	#print(maxk)
	print(b - maxk * ag)
t = int(input())
for i in range(t):
	main()