time limit per test 2 second memory limit per test 256 megabytes
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?
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≤1e9; 0≤p≤q≤1e9; 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.
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.
问(x+c1)/(y+c1+c2)什么时候等于p/q 比赛时想到二分了，但二分错位置了 首先能变到的肯定都是p/q的倍数，即p×t/q×t 那么可以二分倍数t 满足的情况是 q×t-y>=0&&p×t-x>=0&&q×t-y>=p×t-x 差距是单调的 所以可以二分## AC code:(不包含输入类)