#include <bits/stdc++.h>
using std::cerr;
using std::endl;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int MAXN = 100005;
int n;
std::set<long long> st;
struct point {
  long long pos, g;
  inline friend bool operator<(point x, point y) { return x.g < y.g; }
} a[MAXN];
int main() {
  int T = read();
  while (T--) {
    n = 0;
    st.clear();
    long long l = read(), r = read(), p = read(), q = read(), mod = (q << 1);
    long long len = r - l + 1, siz = sqrt(len);
    for (int i = (l); i <= (l + siz - 1); ++i) {
      if (st.find(2ll * p * i % mod) != st.end()) continue;
      a[++n] = (point){i, 2ll * p * i % mod};
      st.insert(2ll * p * i % mod);
    }
    std::sort(a + 1, a + n + 1);
    long long lim = len / siz, ans = -1, mind = 1e18;
    for (int i = (0); i <= (lim - 1); ++i) {
      long long mid = (q - 2ll * p * siz * i % mod + mod) % mod;
      int nxt = std::upper_bound(a + 1, a + n + 1, (point){0, mid}) - a;
      int prv = nxt - 1;
      if (prv == 0) prv = n;
      if (nxt == n + 1) nxt = 1;
      if (ans == -1 || (mid - a[prv].g + mod) % mod < mind ||
          ((mid - a[prv].g + mod) % mod == mind && siz * i + a[prv].pos < ans))
        mind = (mid - a[prv].g + mod) % mod, ans = siz * i + a[prv].pos;
      if (ans == -1 || (a[nxt].g - mid + mod) % mod < mind ||
          ((a[nxt].g - mid + mod) % mod == mind && siz * i + a[nxt].pos < ans))
        mind = (a[nxt].g - mid + mod) % mod, ans = siz * i + a[nxt].pos;
    }
    for (int i = (l + lim * siz); i <= (r); ++i) {
      if (ans == -1 ||
          std::min((2ll * p * i - q + mod) % mod,
                   (q - 2ll * p * i % mod + mod) % mod) < mind ||
          (std::min((2ll * p * i - q + mod) % mod,
                    (q - 2ll * p * i % mod + mod) % mod) == mind &&
           i < ans))
        mind = std::min((2ll * p * i - q + mod) % mod,
                        (q - 2ll * p * i % mod + mod) % mod),
        ans = i;
    }
    printf("%I64d\n", ans);
  }
  return 0;
}
