#include <bits/stdc++.h>
using namespace std;
long long f() {
  long long a, b, p, q;
  cin >> a >> b >> p >> q;
  long long sz = 1;
  while (sz * sz < b - a + 1) ++sz;
  const auto md = [&q](const long long x) {
    return (x % (2 * q) + 2 * q) % (2 * q);
  };
  const auto mdAbs = [&md](const long long x) { return min(md(x), md(-x)); };
  vector<pair<long long, long long>> v;
  for (int i = 0; i < sz; ++i) v.emplace_back(md(2 * p * i), i);
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end(),
                 [](const pair<long long, long long> &p1,
                    const pair<long long, long long> &p2) {
                   return p1.first == p2.first;
                 }),
          v.end());
  pair<long long, long long> res = {1LL << 60, -1};
  auto eval = [&](const long long i) {
    assert(a <= i && i <= b);
    return pair<long long, long long>(mdAbs(q - 2 * p * i), i);
  };
  for (int i = 0; a + i * sz + sz - 1 <= b; ++i) {
    const long long diff = md(q - 2 * p * (a + i * sz));
    auto it =
        lower_bound(v.begin(), v.end(), pair<long long, long long>{diff, -1});
    if (it == v.end()) it = v.begin();
    assert(eval(a + i * sz + it->second).first == mdAbs(it->first - diff));
    res = min(res, {mdAbs(it->first - diff), a + i * sz + it->second});
    (it == v.begin() ? it = v.end() : it)--;
    assert(eval(a + i * sz + it->second).first == mdAbs(it->first - diff));
    res = min(res, {mdAbs(it->first - diff), a + i * sz + it->second});
  }
  for (int i = max(a, b - sz); i <= b; ++i) res = min(res, eval(i));
  return res.second;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int T;
  cin >> T;
  while (T--) cout << f() << endl;
  return 0;
}
