#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
long long t, a, b, p, q, rt, goal, mod, base, bbase, qwq;
pair<long long, long long> bst[N];
long long dis(long long u) {
  u %= mod;
  return min(min(abs(u - q), abs(u + q)), abs(u - q - mod));
}
long long plu(long long u, long long v) {
  return ((unsigned)u + (unsigned)v) % mod;
}
long long bsa(long long l, long long r, long long u) {
  if (l == r) {
    return bst[l].second;
  }
  long long mid = (l + r + 1) >> 1;
  if (bst[mid].first <= u) {
    return bsa(mid, r, u);
  } else {
    return bsa(l, mid - 1, u);
  }
}
long long bsb(long long l, long long r, long long u) {
  if (l == r) {
    return bst[l].second;
  }
  long long mid = (l + r) >> 1;
  if (bst[mid].first >= u) {
    return bsb(l, mid, u);
  } else {
    return bsb(mid + 1, r, u);
  }
}
long long solve() {
  mod = q << 1;
  base = (p << 1) % mod;
  rt = (long long)ceil(sqrt(b - a + 1));
  bbase = (long long)((long long)base * rt % mod);
  goal = (long long)((long long)base * a % mod);
  long long mnd = dis(goal), pos = a, rep, repg;
  for (long long i = 1; i < rt; i++) {
    bst[i] = make_pair((long long)((long long)base * i % mod), i);
    if (dis(plu(goal, bst[i].first)) < mnd ||
        (dis(plu(goal, bst[i].first)) == mnd && a + i < pos)) {
      mnd = dis(plu(goal, bst[i].first));
      pos = a + i;
    }
  }
  bst[rt] = make_pair(0, 0);
  sort(bst + 1, bst + rt + 1);
  for (long long i = 1; i <= rt; i++) {
    bst[i + rt] = make_pair(bst[i].first + mod, bst[i].second);
  }
  long long i, j;
  for (i = 1, j = bbase; i * rt < b - a - rt + 1; i++, j = (j + bbase) % mod) {
    repg = (long long)(((long long)mod + q - plu(goal, j)));
    rep = bsb(1, rt << 1, repg);
    if (dis((long long)((long long)base * (i * rt + rep + a) % mod)) < mnd ||
        (dis((long long)((long long)base * (i * rt + rep + a) % mod)) == mnd &&
         a + i * rt + rep < pos)) {
      mnd = dis((long long)((long long)base * (i * rt + rep + a) % mod));
      pos = a + i * rt + rep;
    }
    rep = bsa(1, rt << 1, repg);
    if (dis((long long)((long long)base * (i * rt + rep + a) % mod)) < mnd ||
        (dis((long long)((long long)base * (i * rt + rep + a) % mod)) == mnd &&
         a + i * rt + rep < pos)) {
      mnd = dis((long long)((long long)base * (i * rt + rep + a) % mod));
      pos = a + i * rt + rep;
    }
  }
  for (i = a + i * rt; i <= b; i++) {
    if (dis((long long)((long long)base * i % mod)) < mnd ||
        (dis((long long)((long long)base * i % mod)) == mnd && i < pos)) {
      mnd = dis((long long)((long long)base * i % mod));
      pos = i;
    }
  }
  return pos;
}
signed main() {
  scanf("%lld", &t);
  for (long long tt = 1; tt <= t; tt++) {
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    if (a == b) {
      printf("%lld\n", a);
      continue;
    }
    printf("%lld\n", solve());
  }
  return 0;
}
