A. Success Rate

Codeforces

IDCF806A

Time2000ms

Memory256MB

Difficulty—

binary searchmath

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.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "A. Success Rate",
    "description": {
      "content": "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 rat",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF806A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 rat...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments