#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
struct node {
  long long v;
  long long id;
  node(long long v, long long id) {
    this->v = v;
    this->id = id;
  }
  node() {}
};
bool operator<(node A, node B) {
  if (A.v == B.v)
    return A.id < B.id;
  else
    return A.v < B.v;
}
node a[MAXN];
int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  for (int k = (1); k <= (T); k += (1)) {
    long long l, r, p, q;
    cin >> l >> r >> p >> q;
    long long step = sqrt(r - l + 1), tot = 0, val = 0x007F7F7F7F7F7F7FLL,
              ans = -0x007F7F7F7F7F7F7FLL;
    long long p2 = 2LL * p, q2 = 2LL * q;
    for (int i = (l); i <= (r); i += (step)) {
      if (i + step - 1 <= r) {
        tot++;
        a[tot] = node(i * p2 % q2, i);
      } else {
        for (int j = (i); j <= (r); j += (1)) {
          long long cur = abs(j * p2 % q2 - q);
          if (cur < val || (cur == val && j < ans)) {
            val = cur;
            ans = j;
          }
        }
      }
    }
    sort(a + 1, a + 1 + tot);
    long long tot2 = 1;
    for (int i = (2); i <= (tot); i += (1))
      if (a[i].v != a[tot2].v) {
        tot2++;
        a[tot2] = a[i];
      }
    long long cur = 0;
    for (int i = (0); i <= (step - 1); i += (1)) {
      long long pos = (q - cur + 2LL * q) % q2;
      int k = lower_bound(a + 1, a + 1 + tot2, node(pos, -1)) - a;
      if (k <= tot2) {
        if (a[k].v - pos < val || (a[k].v - pos == val && a[k].id + i < ans)) {
          val = a[k].v - pos;
          ans = a[k].id + i;
        }
      } else {
        if (2LL * q - (pos - a[1].v) < val ||
            (2LL * q - (pos - a[1].v) == val && a[1].id + i < ans)) {
          val = 2LL * q - (pos - a[1].v);
          ans = a[1].id + i;
        }
      }
      k--;
      if (k >= 1) {
        if (pos - a[k].v < val || (pos - a[k].v == val && a[k].id + i < ans)) {
          val = pos - a[k].v;
          ans = a[k].id + i;
        }
      } else {
        if (2LL * q - (a[tot2].v - pos) < val ||
            (2LL * q - (a[tot2].v - pos) == val && a[tot2].id + i < ans)) {
          val = 2LL * q - (a[tot2].v - pos);
          ans = a[tot2].id + i;
        }
      }
      cur = (cur + p2) % q2;
    }
    cout << ans << endl;
  }
  return 0;
}
