#include <bits/stdc++.h>
using namespace std;
const int N = 64000;
int T, a, b, p, q, mi, ans, n, G;
pair<long long, int> res[N], A[N];
bool cmp(pair<long long, int> a, pair<long long, int> b) {
  return a.first < b.first || a.first == b.first && a.second > b.second;
}
int Find(long long x) {
  int l, r, mid;
  for (l = 1, r = n, mid = l + r >> 1; l < r; mid = l + r >> 1) {
    if (A[mid].first < x)
      l = mid + 1;
    else
      r = mid;
  }
  return mid;
}
void work() {
  scanf("%d%d%d%d", &a, &b, &p, &q);
  mi = q + 1;
  G = sqrt(b - a + 1);
  for (int i = 0; i < G; i++) res[i + 1] = make_pair(2ll * p * i % (2 * q), i);
  sort(res + 1, res + G + 1, cmp);
  n = 0;
  for (int i = 1; i <= G; i++)
    if (i == G || res[i].first < res[i + 1].first) A[++n] = res[i];
  for (int i = 1; i <= n; i++) A[i + n] = A[i], A[i + n].first += 2 * q;
  n <<= 1;
  for (int r, x; a + G <= b; a += G) {
    r = 2ll * p * a % (2 * q);
    long long y;
    if (r <= q) {
      x = Find(q - r);
      y = A[x].first - q + r;
      if (y < 0) y = -y;
      if (y < mi) mi = y, ans = A[x].second + a;
      x--;
      y = q - r - A[x].first;
      if (y < 0) y = -y;
      if (x && (y < mi || y == mi && A[x].second + a < ans))
        mi = y, ans = A[x].second + a;
    }
    x = Find(3ll * q - r);
    y = A[x].first - 3ll * q + r;
    if (y < 0) y = -y;
    if (y < mi) mi = y, ans = A[x].second + a;
    x--;
    y = 3ll * q - r - A[x].first;
    if (y < 0) y = -y;
    if (x && (y < mi || y == mi && A[x].second + a < ans))
      mi = y, ans = A[x].second + a;
  }
  for (int r; a <= b; a++) {
    r = 2ll * p * a % (2 * q);
    r = (r <= q) ? q - r : r - q;
    if (r < mi) mi = r, ans = a;
  }
  printf("%d\n", ans);
}
int main() {
  for (scanf("%d", &T); T--; work())
    ;
  return 0;
}
