#include <bits/stdc++.h>
using namespace std;
const long long INFll = 1ll << 60;
long long Li, Ri, p, q;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) return x = 1, y = 0, void();
  exgcd(b, a % b, y, x);
  y -= (a / b) * x;
}
long long sub_f(long long a, long long b, long long c, long long n) {
  if (n <= 0) return 0;
  return n * (n - 1) / 2 * (a / c) + n * (b / c) +
         sub_f(c, (a * n + b) % c, a % c, (a % c * n + b % c) / c);
}
long long calc(long long a, long long b, long long c, long long n) {
  if (c < 0) {
    c = -c;
    a = -a, b = -b;
    return calc(a, b, c, n);
  }
  if (a < 0) {
    a = -a;
    return calc(a, b - a * (n - 1), c, n);
  }
  if (b < 0) {
    b = -b;
    long long k = b / c + (b % c != 0);
    return calc(a, k * c - b, c, n) - k * n;
  }
  return sub_f(a, b, c, n);
}
bool Chk(long long M) {
  long long sec1 =
      calc(2 * p, -q + M, 2 * q, Ri + 1) - calc(2 * p, -q + M, 2 * q, Li);
  long long sec2 = calc(2 * p, -q - M - 1, 2 * q, Ri + 1) -
                   calc(2 * p, -q - M - 1, 2 * q, Li);
  return sec1 - sec2 > 0;
}
long long solve(long long a, long long b, long long m) {
  b = (b % m + m) % m;
  a = (a % m + m) % m;
  long long d = gcd(a, m);
  if (b % d) return INFll;
  long long x, y, Mod = m / d;
  exgcd(a / d, Mod, x, y);
  x = (x % Mod + Mod) % Mod;
  long long tmp = x * (b / d) % Mod;
  long long final_ans = Li + ((tmp % Mod) - (Li % Mod) + Mod) % Mod;
  return final_ans;
}
void solve() {
  scanf("%lld%lld%lld%lld", &Li, &Ri, &p, &q);
  long long d = gcd(p, q);
  p /= d, q /= d;
  long long L = 0, R = q, M = q;
  while (L <= R) {
    long long Mid = (L + R) >> 1;
    if (Chk(Mid))
      M = Mid, R = Mid - 1;
    else
      L = Mid + 1;
  }
  printf("%lld\n", min(solve(2 * p, q - M, 2 * q), solve(2 * p, q + M, 2 * q)));
}
int main() {
  int t;
  for (scanf("%d", &t); t--; solve())
    ;
}
