#include <bits/stdc++.h>
using namespace std;
const int N = 80000 + 10;
int rd() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * w;
}
int l, r, n, p, q;
struct node {
  long long x;
  int i;
  bool operator<(const node &bb) const {
    return x != bb.x ? x < bb.x : i < bb.i;
  }
} a[N];
int main() {
  int T = rd();
  a[0].x = -1;
  while (T--) {
    int ans = 0, mx = 1 << 30;
    l = rd(), r = rd(), p = rd(), q = rd();
    n = r - l + 1;
    int kk = sqrt(n), mod = 2 * q;
    for (int i = 0; i < kk; ++i) a[i + 1] = (node){2ll * p * (l + i) % mod, i};
    sort(a + 1, a + kk + 1);
    int m = 0;
    for (int i = 1; i <= kk; ++i)
      if (a[i].x != a[i - 1].x) a[++m] = a[i];
    int ii;
    for (ii = l; ii + kk - 1 <= r; ii += kk) {
      int zz = ((1ll * q - 2ll * p * (ii - l) % mod) % mod + mod) % mod;
      int ps = upper_bound(a + 1, a + m + 1, (node){zz, 0}) - a, nw;
      ps = (ps - 1) % m + 1;
      nw = min(abs(1ll * a[ps].x - zz), min(abs(1ll * a[ps].x + mod - zz),
                                            abs(1ll * a[ps].x - mod - zz)));
      if (mx > nw || (mx == nw && ans > a[ps].i + ii))
        ans = a[ps].i + ii, mx = nw;
      ps = (ps + m - 2) % m + 1;
      nw = min(abs(1ll * a[ps].x - zz), min(abs(1ll * a[ps].x + mod - zz),
                                            abs(1ll * a[ps].x - mod - zz)));
      if (mx > nw || (mx == nw && ans > a[ps].i + ii))
        ans = a[ps].i + ii, mx = nw;
    }
    while (ii <= r) {
      int nw = abs(2ll * p * ii % mod - q);
      if (mx > nw || (mx == nw && ans > ii)) ans = ii, mx = nw;
      ++ii;
    }
    printf("%d\n", ans);
  }
  return 0;
}
