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.
[samples]
## 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.
你是一位有经验的 Codeforces 用户。今天你发现，在你于 Codeforces 上的活动中，你共提交了 #cf_span[y] 次，其中 #cf_span[x] 次成功。因此，你在 Codeforces 上的当前成功率是 #cf_span[x / y]。
你最喜欢的区间 #cf_span[[0;1]] 内的有理数是 #cf_span[p / q]。现在你想知道：为了让你的成功率达到 #cf_span[p / q]，你最少需要再提交多少次？
第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 1000]) —— 测试用例的数量。
接下来的 #cf_span[t] 行，每行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[p] 和 #cf_span[q] (#cf_span[0 ≤ x ≤ y ≤ 10^9]; #cf_span[0 ≤ p ≤ q ≤ 10^9]; #cf_span[y > 0]; #cf_span[q > 0])。
保证 #cf_span[p / q] 是一个最简分数。
*黑客*。对于黑客测试，必须满足额外约束 #cf_span[t ≤ 5]。
对于每个测试用例，请输出一个整数，表示为了让你的成功率等于你最喜欢的有理数，你最少需要再提交的次数；如果无法实现，则输出 _-1_。
在第一个例子中，你需要再进行 4 次成功提交。你的成功率将变为 #cf_span[7 / 14]，即 #cf_span[1 / 2]。
在第二个例子中，你需要再进行 2 次成功和 8 次失败提交。你的成功率将变为 #cf_span[9 / 24]，即 #cf_span[3 / 8]。
在第三个例子中，无需进行任何新提交。你的成功率已经是 #cf_span[20 / 70]，即 #cf_span[2 / 7]。
在第四个例子中，唯一的一次失败提交破坏了你达到成功率 1 的希望。
## Input
第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 1000]) —— 测试用例的数量。接下来的 #cf_span[t] 行，每行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[p] 和 #cf_span[q] (#cf_span[0 ≤ x ≤ y ≤ 10^9]; #cf_span[0 ≤ p ≤ q ≤ 10^9]; #cf_span[y > 0]; #cf_span[q > 0])。保证 #cf_span[p / q] 是一个最简分数。*黑客*。对于黑客测试，必须满足额外约束 #cf_span[t ≤ 5]。
## Output
对于每个测试用例，请输出一个整数，表示为了让你的成功率等于你最喜欢的有理数，你最少需要再提交的次数；如果无法实现，则输出 _-1_。
[samples]
## Note
在第一个例子中，你需要再进行 4 次成功提交。你的成功率将变为 #cf_span[7 / 14]，即 #cf_span[1 / 2]。在第二个例子中，你需要再进行 2 次成功和 8 次失败提交。你的成功率将变为 #cf_span[9 / 24]，即 #cf_span[3 / 8]。在第三个例子中，无需进行任何新提交。你的成功率已经是 #cf_span[20 / 70]，即 #cf_span[2 / 7]。在第四个例子中，唯一的一次失败提交破坏了你达到成功率 1 的希望。
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, t\} $, let:
- $ x_k, y_k \in \mathbb{Z}_{\geq 0} $ be the current number of successful and total submissions, respectively, with $ 0 \leq x_k \leq y_k $ and $ y_k > 0 $,
- $ p_k, q_k \in \mathbb{Z}_{\geq 0} $ be the numerator and denominator of the target irreducible fraction, with $ 0 \leq p_k \leq q_k $ and $ q_k > 0 $.
**Constraints**
1. $ 1 \leq t \leq 1000 $
2. For each $ k $:
- $ 0 \leq x_k \leq y_k \leq 10^9 $
- $ 0 \leq p_k \leq q_k \leq 10^9 $
- $ \gcd(p_k, q_k) = 1 $
**Objective**
Find the smallest non-negative integer $ d $ such that there exist non-negative integers $ a, b $ with:
- $ a \geq 0 $: additional successful submissions,
- $ b \geq 0 $: additional total submissions (so $ b \geq a $),
- $ d = a + b $,
- $ \frac{x_k + a}{y_k + b} = \frac{p_k}{q_k} $.
If no such $ d $ exists, output $ -1 $.
Equivalently, find the minimal $ d \geq 0 $ such that:
$$
\exists \, n \in \mathbb{Z}_{>0} \text{ with } n p_k \geq x_k, \; n q_k \geq y_k, \; \text{and} \; d = n q_k - y_k
$$
and $ n p_k - x_k \leq n q_k - y_k $ (which is always true since $ p_k \leq q_k $).
Thus, minimize $ d = n q_k - y_k $ over integers $ n \geq \max\left( \left\lceil \frac{x_k}{p_k} \right\rceil, \left\lceil \frac{y_k}{q_k} \right\rceil \right) $ if $ p_k > 0 $, or if $ p_k = 0 $, then $ x_k = 0 $ and $ n \geq \left\lceil \frac{y_k}{q_k} \right\rceil $.
If $ p_k = 0 $ and $ x_k > 0 $, output $ -1 $.
If $ p_k = q_k $ and $ x_k < y_k $, output $ -1 $ (since we cannot reduce failure rate to 0).