跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0893. Success Rate

  • ID: 899
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:进阶
  • 上传者:
  • 二分
  • 数学
  • 算法思想
  • 进阶
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Success Rate

题目描述

A. Success Rate
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1
Output
4
10
0
-1
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.


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 326 题。保留原作者与原赛事署名。