#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
using cd = complex<ld>;
using vcd = vector<cd>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<ld>;
using vs = vector<string>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T> >;
template <class T>
inline int ckmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int ckmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
template <class T>
void remDup(vector<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), end(v));
}
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }
constexpr int p2(int x) { return 1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }
ll ceilDiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll floorDiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
void setPrec(int x) { cout << fixed << setprecision(x); }
string to_string(char c) { return string(1, c); }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(bool b) { return to_string((int)b); }
template <class T>
string to_string(complex<T> c) {
  stringstream ss;
  ss << c;
  return ss.str();
}
template <class T>
using V = vector<T>;
string to_string(V<bool> v) {
  string res = "{";
  for (int i = (0); i <= (int((v).size()) - 1); i++) res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t sz>
string to_string(bitset<sz> b) {
  string res = "";
  for (int i = (0); i <= (int((b).size()) - 1); i++) res += char('0' + b[i]);
  return res;
}
template <class T, class U>
string to_string(pair<T, U> p);
template <class T>
string to_string(T v) {
  bool fst = 1;
  string res = "";
  for (const auto& x : v) {
    if (!fst) res += " ";
    fst = 0;
    res += to_string(x);
  }
  return res;
}
template <class T, class U>
string to_string(pair<T, U> p) {
  return "(" + to_string(p.f) + ", " + to_string(p.s) + ")";
}
template <class T>
void pr(T x) {
  cout << to_string(x);
}
template <class T, class... U>
void pr(const T& t, const U&... u) {
  pr(t);
  pr(u...);
}
void ps() { pr("\n"); }
template <class T, class... U>
void ps(const T& t, const U&... u) {
  pr(t);
  if (sizeof...(u)) pr(" ");
  ps(u...);
}
void DBG() { cerr << "]" << endl; }
template <class T, class... U>
void DBG(const T& t, const U&... u) {
  cerr << to_string(t);
  if (sizeof...(u)) cerr << ", ";
  DBG(u...);
}
const ld PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld EPS = 1e-9;
const ll MODBASE = 1000000007LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 110;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;
ll solve(ll l, ll r, ll p, ll q) {
  ll seg = 1;
  while (seg * seg < r - l) seg++;
  vpl firstSeg;
  for (ll i = l; i < l + seg; i++) {
    ll x = 2 * p * i % (2 * q);
    firstSeg.push_back({x, i});
  }
  sort(firstSeg.begin(), firstSeg.end());
  vpl tmp = firstSeg;
  firstSeg.clear();
  firstSeg.push_back(tmp[0]);
  for (int i = (1); i <= (int((tmp).size()) - 1); i++)
    if (tmp[i].first != tmp[i - 1].first) firstSeg.push_back(tmp[i]);
  ll res = -1, val = (ll)INF * INF, itr = 0;
  for (itr = 0; l + (itr + 1) * seg <= r; itr++) {
    ll z = q - 2 * p * itr * seg;
    z %= 2 * q;
    if (z < 0) z += 2 * q;
    ll baseIdx =
        lower_bound(firstSeg.begin(), firstSeg.end(), pl(z, (ll)-INF * INF)) -
        firstSeg.begin();
    for (int j = (0); j >= (-1); j--) {
      ll checkIdx = (baseIdx + j) % int((firstSeg).size());
      if (checkIdx < 0) checkIdx += int((firstSeg).size());
      ll thisNum = firstSeg[checkIdx].second + itr * seg;
      ll w = z - firstSeg[checkIdx].first;
      if (w < 0) w = -w;
      if (w > q) w = 2 * q - w;
      if (w < val) {
        val = w;
        res = thisNum;
      } else if (w == val && thisNum < res) {
        val = w;
        res = thisNum;
      }
    }
  }
  for (ll i = l + itr * seg; i < r; i++) {
    ll w = 2 * p * i % (2 * q) - q;
    if (w < 0) w = -w;
    if (w < val) {
      val = w;
      res = i;
    }
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  int te;
  cin >> te;
  while (te--) {
    ll a, b, p, q;
    cin >> a >> b >> p >> q;
    cout << solve(a, b + 1, p, q) << "\n";
  }
  return 0;
}
