#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1.0);
const long long LINF = (long long)1e18 + 5;
const int INF = (int)1e9 + 5;
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T abs(T x) {
  return x < 0 ? -x : x;
}
template <class T>
long long round(T x) {
  return x < 0 ? x - 0.5 : x + 0.5;
}
template <class T>
bool chmin(T& x, const T& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T& x, const T& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const pair<P, Q>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  bool was = false;
  os << "{";
  for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
  bool was = false;
  os << "{";
  for (typename set<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  bool was = false;
  os << "{";
  for (typename multiset<T>::const_iterator it = v.begin(); it != v.end();
       it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const map<P, Q>& v) {
  bool was = false;
  os << "{";
  for (typename map<P, Q>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
string nextToken() {
  static char str[(int)1e6 + 5];
  scanf("%s", str);
  return str;
}
template <class T>
T nextInt() {
  long long x = 0;
  bool p = false;
  char c;
  do {
    c = getchar();
  } while (c <= 32);
  if (c == '-') {
    p = true;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return (p ? -x : x);
}
long long gcd(long long x, long long y) {
  while (x && y) {
    if (x > y)
      x %= y;
    else
      y %= x;
  }
  return x + y;
}
bool inRange(long long l, long long r, long long x) { return x >= l && x <= r; }
bool can(long long x, long long y, long long p, long long q) {
  if (x > p) return false;
  if (y > q) return false;
  long long remQ = q - y;
  long long remP = p - x;
  if (remP > remQ) return false;
  return true;
}
long long foo(long long x, long long y, long long p, long long q) {
  return q - y;
}
long long go(long long x, long long y, long long p, long long q) {
  long long l = 0, r = LINF / q + 1;
  while (r - l > 1) {
    long long mid = (l + r) >> 1;
    if (can(x, y, p * mid, q * mid))
      r = mid;
    else
      l = mid;
  }
  long long mid = r;
  if (!can(x, y, p * mid, q * mid)) return -1;
  return foo(x, y, p * mid, q * mid);
}
void tr(long long& x, long long& y) {
  long long g = gcd(x, y);
  x /= g;
  y /= g;
}
int main(int argc, char* argv[]) {
  int t;
  cin >> t;
  while (t--) {
    long long x, y, p, q;
    cin >> x >> y >> p >> q;
    tr(p, q);
    cout << go(x, y, p, q) << endl;
  }
}

### Prompt

Generate a cpp solution to the following problem:

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;
const long double PI = acos(-1.0);
const long long LINF = (long long)1e18 + 5;
const int INF = (int)1e9 + 5;
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T abs(T x) {
  return x < 0 ? -x : x;
}
template <class T>
long long round(T x) {
  return x < 0 ? x - 0.5 : x + 0.5;
}
template <class T>
bool chmin(T& x, const T& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T& x, const T& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const pair<P, Q>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  bool was = false;
  os << "{";
  for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
  bool was = false;
  os << "{";
  for (typename set<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  bool was = false;
  os << "{";
  for (typename multiset<T>::const_iterator it = v.begin(); it != v.end();
       it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const map<P, Q>& v) {
  bool was = false;
  os << "{";
  for (typename map<P, Q>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
string nextToken() {
  static char str[(int)1e6 + 5];
  scanf("%s", str);
  return str;
}
template <class T>
T nextInt() {
  long long x = 0;
  bool p = false;
  char c;
  do {
    c = getchar();
  } while (c <= 32);
  if (c == '-') {
    p = true;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return (p ? -x : x);
}
long long gcd(long long x, long long y) {
  while (x && y) {
    if (x > y)
      x %= y;
    else
      y %= x;
  }
  return x + y;
}
bool inRange(long long l, long long r, long long x) { return x >= l && x <= r; }
bool can(long long x, long long y, long long p, long long q) {
  if (x > p) return false;
  if (y > q) return false;
  long long remQ = q - y;
  long long remP = p - x;
  if (remP > remQ) return false;
  return true;
}
long long foo(long long x, long long y, long long p, long long q) {
  return q - y;
}
long long go(long long x, long long y, long long p, long long q) {
  long long l = 0, r = LINF / q + 1;
  while (r - l > 1) {
    long long mid = (l + r) >> 1;
    if (can(x, y, p * mid, q * mid))
      r = mid;
    else
      l = mid;
  }
  long long mid = r;
  if (!can(x, y, p * mid, q * mid)) return -1;
  return foo(x, y, p * mid, q * mid);
}
void tr(long long& x, long long& y) {
  long long g = gcd(x, y);
  x /= g;
  y /= g;
}
int main(int argc, char* argv[]) {
  int t;
  cin >> t;
  while (t--) {
    long long x, y, p, q;
    cin >> x >> y >> p >> q;
    tr(p, q);
    cout << go(x, y, p, q) << endl;
  }
}

```