codeforces round # 412 c(数论)

本文主要是介绍codeforces round # 412 c(数论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 ≤ 10⁹; 0 ≤ p ≤ q ≤ 10⁹; 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

Output

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.

/*借鉴原文地址http://blog.csdn.net/dormousenone/article/details/71404361*/

/*题意

记 AC 率为当前 AC 提交的数量 x / 总提交量 y 。已知最喜欢的 AC 率为 p/q (pq∈[0,1]) 。求最少在提交多少题（AC or NOT）能恰好达到 AC 率为 p/q 。

解题思路

记 P/Q 为 p/q 的最简比（P 与 Q 互质）。

问题可以转化为求最小的 n 满足 nPnQ=x+ay+b ，其中 a 为新提交的 AC 题数，b 为新提交的题数。

由于 nP , nQ, x+a, y+b 都为整数，故可将等式化为 nP=x+a 且 nQ=y+b ，两个方程三个未知数，故该方程若有解即多解。求最小的 n 。同时，可以考虑到存在额外的条件：0≤(a=nP−x)≤(b=nQ−y) ，化简可得到 n≥⌈xP⌉ 且 n≥⌈y−xQ−P⌉ ，求两者的最大值即为满足条件的最小的 n。此题求最少的新提交题数，ans=b=nQ−y 。

同时，需注意特殊点：p=q 或 p=0 的情况。还要注意输入lld 还是 %I64d*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;long long x, y, p, q;int main()
{int t;scanf("%d", &t);while(t--){scanf("%I64d%I64d%I64d%I64d", &x, &y, &p, &q);if(p == q){printf("%d\n", x == y ? 0 : -1);continue;}if(p == 0){printf("%d\n", x == 0 ? 0 : -1);continue;}long long gcd = __gcd(p, q);p /= gcd, q /= gcd;long long n = max(ceil(x*1.0/p), ceil((y-x)*1.0/(q-p)));printf("%I64d\n", n * q - y);}return 0;
}

这篇关于codeforces round # 412 c(数论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！