This basketball season, Petriukas has attempted y shots, out of which x were successful. His shooting accuracy is x/y.
Petriukas wants to match his coach, who has already retired and had a career shooting accuracy of a/b.
Help determine the minimum number of additional shots Petriukas must make so that his accuracy becomes exactly equal to that of his coach.
You are given t independent test cases.
Input
The first line contains a single integer t (1 \le t \le 1000) — the number of test cases.
Each of the following t lines contains four integers: x, y, a, and b
(0 \le x \le y \le 10^9; 0 \le a \le b \le 10^9; y > 0; b > 0).
It is guaranteed that the fraction a/b is irreducible (in lowest terms).
Output
For each test case, print the minimum number of additional shots Petriukas must make to match his coach’s accuracy exactly.
If it is impossible, print -1.
Example
| standard input | standard output |
|---|
| 3
3 10 1 2
7 14 3 8
20 70 2 7
| 4
10
0
|