#include <bits/stdc++.h>
using namespace std;
long long xinyue, a, b, p, q, len;
long long calc(long long a, long long b, long long c, long long n) {
  if (!a || !n) return (n + 1) * (b / c);
  if (n < 0) return 0;
  long long m = (a * n + b) / c;
  if (a >= c || b >= c)
    return calc(a % c, b % c, c, n) + (n * (n + 1) >> 1) * (a / c) +
           (n + 1) * (b / c);
  return m * n - calc(c, c - b - 1, a, m - 1);
}
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  long long g = gcd(b, a % b, y, x);
  y -= a / b * x;
  return g;
}
int main() {
  scanf("%lld", &xinyue);
  while (xinyue--) {
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    long long l = 0, r = q, P = p << 1, Q = q << 1;
    while (l < r) {
      long long mid = l + r >> 1;
      long long L = q - mid, R = q + mid + 1;
      if (calc(P, Q - L, Q, b) + calc(P, Q - R, Q, a - 1) -
              calc(P, Q - L, Q, a - 1) - calc(P, Q - R, Q, b) >
          0)
        r = mid;
      else
        l = mid + 1;
    }
    long long x, y, g = gcd(P, Q, x, y), ans = 1e9;
    P /= g;
    Q /= g;
    if ((q - l) % g == 0) {
      long long xx = (q - l) / g * x;
      xx += (a - xx) / Q * Q;
      while (xx >= a) xx -= Q;
      while (xx < a) xx += Q;
      ans = min(ans, xx);
    }
    if ((q + l) % g == 0) {
      long long xx = (q + l) / g * x;
      xx += (a - xx) / Q * Q;
      while (xx >= a) xx -= Q;
      while (xx < a) xx += Q;
      ans = min(ans, xx);
    }
    printf("%lld\n", ans);
  }
}
