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.
tc = int(input())
for i in range(tc):
	x, y, p, q = map(int, input().split())
	if p == 0:
		if x == 0:
			print('0')
		else:
			print('-1')
	elif p == q:
		if y > x:
			print('-1')
		else:
			print('0')
	elif p * y == x * q:
		print('0')
	else:
		#newy = y
		#while True:
		#	newy += q - (newy % q)
		#	newx = (newy // q) * p
		#	if 0 <= newx - x <= newy - y:
		#		print(str(newy - y))
		#		break
		def minmax(lob, hib):
			if lob == hib:
				return lob - y
			lower = (lob + hib) // 2
			higher = lower + q - (lower % q)
			lower = higher - q
			newxh = (higher // q) * p
			if 0 <= newxh - x <= higher - y:
				newxl = (lower // q) * p
				if 0 <= newxl - x <= lower - y:
					return minmax(lob, lower)
				else:
					return higher - y
			else:
				return minmax(higher, hib)
		lob = y + q - (y % q)
		hib = 10**19 + q - (10**19 % q)
		print(str(minmax(lob, hib)))
