Success Rate
Contest: VK Cup 2017 - Round 3
Difficulty rating: 1700
Tags: binary search, math

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1

Example output:
4
10
0
-1

Editorial:
This problem can be solved using binary search without any special cases. You can also solve it using a formula, handling a couple of special cases separately.
If our success rate is p / q, it means we have pt successful submissions out of qt for some t. Since p / q is already irreducible, t has to be a positive integer.
Let's reformulate things a bit. Initially we have x successful submissions and y - x unsuccessful ones. Suppose we fix t, and in the end we want to have pt successful submissions and qt - pt unsuccessful ones. It's clear we can achieve that if pt ≥ x and qt - pt ≥ y - x, since we can only increase both the number of successful and unsuccessful submissions.
Note that both inequalities have constant right hand side, and their left hand side doesn't decrease as t increases. Therefore, if the inequalities are satisfied for some t, they will definitely be satisfied for larger t as well.
It means we can apply binary search to find the lowest value of t satisfying the inequality. Then, the answer to the problem is qt - y. If even for very large t the inequalities are not satisfied, the answer is -1.
It can be proved that one "very large" value of t is t = y — that is, if the inequalities are not satisfied for t = y, then they cannot be satisfied for any value of t. Alternatively, picking t = 109 works too, since y ≤ 109.
Actually, inequalities pt ≥ x and qt - pt ≥ y - x are easy to solve by hand. From pt ≥ x it follows that $$t \geq \frac{x}{p}$$. From qt - pt ≥ y - x it follows that $$t \geq \frac{y-x}{q-p}$$. In order to satisfy both inequalities, t has to satisfy $$t \geq \max\left(\frac{x}{p}, \frac{y-x}{q-p}\right)$$.
Don't forget that t has to be integer, so the division results have to be rounded up to the nearest integer. In general, if we want to find $${ \frac { a } { b } }$$ rounded up where both a and b are positive integers, the usual way to do that is to calculate (a + b - 1) / b, where " / " is the standard integer division (rounded down).
In this solution, cases when p / q = 0 / 1 or p / q = 1 / 1 have to be handled separately.