#include <bits/stdc++.h>
using namespace std;
long long cota(long long x, long long y, long long p, long long q) {
  return (long long)max(max(ceil((double)y / q) + 1, ceil((double)x / p)) + 1,
                        ceil((double)(y - x) / (p - q)) + 1);
}
bool cumple(long long m, long long x, long long y, long long p, long long q) {
  if (m * q < y or m * p < x or m * q - y < m * p - x) {
    return false;
  }
  return true;
}
int main() {
  int n;
  cin >> n;
  long long x, y, p, q, mid;
  vector<long long> rta;
  while (n--) {
    cin >> x >> y >> p >> q;
    if (p * y == q * x) {
      rta.push_back(0);
    } else {
      if (p - q == 0) {
        rta.push_back(-1);
      } else {
        long long least = 0, last = 10000000000;
        while (last - least > 1) {
          mid = (last + least) / 2;
          if (cumple(mid, x, y, p, q)) {
            last = mid;
          } else {
            least = mid;
          }
        }
        if (cumple(least, x, y, p, q))
          rta.push_back(least * q - y);
        else {
          if (cumple(last, x, y, p, q))
            rta.push_back(last * q - y);
          else
            rta.push_back(-1);
        }
      }
    }
  }
  for (int i = 0; i < rta.size(); i++) {
    cout << rta[i] << endl;
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long cota(long long x, long long y, long long p, long long q) {
  return (long long)max(max(ceil((double)y / q) + 1, ceil((double)x / p)) + 1,
                        ceil((double)(y - x) / (p - q)) + 1);
}
bool cumple(long long m, long long x, long long y, long long p, long long q) {
  if (m * q < y or m * p < x or m * q - y < m * p - x) {
    return false;
  }
  return true;
}
int main() {
  int n;
  cin >> n;
  long long x, y, p, q, mid;
  vector<long long> rta;
  while (n--) {
    cin >> x >> y >> p >> q;
    if (p * y == q * x) {
      rta.push_back(0);
    } else {
      if (p - q == 0) {
        rta.push_back(-1);
      } else {
        long long least = 0, last = 10000000000;
        while (last - least > 1) {
          mid = (last + least) / 2;
          if (cumple(mid, x, y, p, q)) {
            last = mid;
          } else {
            least = mid;
          }
        }
        if (cumple(least, x, y, p, q))
          rta.push_back(least * q - y);
        else {
          if (cumple(last, x, y, p, q))
            rta.push_back(last * q - y);
          else
            rta.push_back(-1);
        }
      }
    }
  }
  for (int i = 0; i < rta.size(); i++) {
    cout << rta[i] << endl;
  }
  return 0;
}

```