#include <bits/stdc++.h>
using namespace std;
int t, a, b, p, q;
struct node {
  long long a;
  int b;
} up[1000006], down[1000006];
int read() {
  char c = getchar();
  int x = 0;
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  return x;
}
bool comp1(node a, node b) { return a.a < b.a || (a.a == b.a && a.b < b.b); }
bool comp2(node a, node b) { return a.a < b.a || (a.a == b.a && a.b > b.b); }
void update(long long i, int j, int& res, long long& mini) {
  long long cur = abs(i - q);
  if (mini > cur || (mini == cur && j < res)) {
    mini = cur;
    res = j;
  }
}
int solve() {
  int limit = sqrt(b - a + 1) + 1, mod = 2 * q, res = -1;
  long long mini = 0x3f3f3f3f3f3f3f3f;
  for (int i = 1; i <= limit; ++i) {
    up[i].a = 2ll * (a + 1ll * i * limit) * p % mod;
    up[i].b = a + i * limit;
    down[i].a = 2ll * (i - 1) * p % mod;
    down[i].b = i - 1;
  }
  sort(up + 1, up + limit + 1, comp2);
  sort(down + 1, down + limit + 1, comp1);
  for (int i = 1, j = 1; i <= limit && j <= limit; ++i) {
    while (j < limit && down[j + 1].a <= up[i].a &&
           (abs(up[i].a - down[j + 1].a - q) <= abs(up[i].a - down[j].a - q)))
      ++j;
    if (up[i].a < down[j].a || up[i].b - down[j].b > b ||
        up[i].b - down[j].b < a)
      continue;
    update(up[i].a - down[j].a, up[i].b - down[j].b, res, mini);
    if (j > 1)
      update(up[i].a - down[j - 1].a, up[i].b - down[j - 1].b, res, mini);
  }
  for (int i = 1, j = 1; i <= limit && j <= limit; ++i) {
    while (j < limit && up[j + 1].a <= down[i].a &&
           (abs(up[j].a - down[i].a + mod - q) >=
            abs(up[j + 1].a - down[i].a + mod - q)))
      ++j;
    if (up[j].a > down[i].a || up[j].b - down[i].b > b ||
        up[j].b - down[i].b < a)
      continue;
    update(up[j].a - down[i].a + mod, up[j].b - down[i].b, res, mini);
    if (j > 1)
      update(up[j - 1].a - down[i].a + mod, up[j - 1].b - down[i].b, res, mini);
  }
  for (int i = 0; i < limit; ++i) {
    int pos = b - i;
    if (pos < a) break;
    update(2ll * p * pos % mod, pos, res, mini);
  }
  for (int i = 0; i < limit; ++i) {
    int pos = a + i;
    if (pos > b) continue;
    update(2ll * p * pos % mod, pos, res, mini);
  }
  return res;
}
int main() {
  t = read();
  while (t--) {
    a = read();
    b = read();
    p = read();
    q = read();
    printf("%d\n", solve());
  }
}
