#include <bits/stdc++.h>
using namespace std;
const int B = 40000;
pair<int, int> ans, qq[B + 5];
int a, b, p, q;
void solve() {
  ans = pair<int, int>(1 << 30, 0);
  scanf("%d%d%d%d", &a, &b, &p, &q);
  if (b - a + 1 >= B) {
    for (int i = (int)(1); i <= (int)(B); i++)
      qq[i] = pair<int, int>(1ll * p * (i - 1) % q * 2, i - 1);
    sort(qq + 1, qq + B + 1);
    int tp = 1;
    for (int i = (int)(2); i <= (int)(B); i++)
      if (qq[i].first != qq[i - 1].first) qq[++tp] = qq[i];
    for (; b - a + 1 >= B; a += B) {
      int v = 1ll * p * a % q * 2, val;
      int p = lower_bound(qq + 1, qq + tp + 1,
                          pair<int, int>((3ll * q - v) % (2 * q), -1)) -
              qq;
      ans = min(ans, pair<int, int>(
                         abs(q - (1ll * v + qq[(p + tp - 1) % tp + 1].first) %
                                     (2 * q)),
                         a + qq[(p + tp - 1) % tp + 1].second));
      ans = min(ans, pair<int, int>(
                         abs(q - (1ll * v + qq[(p + tp - 2) % tp + 1].first) %
                                     (2 * q)),
                         a + qq[(p + tp - 2) % tp + 1].second));
    }
  }
  for (; a <= b; ++a) {
    int v = 1ll * p * a % q * 2;
    ans = min(ans, pair<int, int>(abs(v - q), a));
  }
  printf("%d\n", ans.second);
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) solve();
}
