#include <bits/stdc++.h>
using namespace std;
long long calc(long long a, long long b, long long c, long long n) {
  if (!n) return 0;
  return (b / c) * n + (a / c) * n * (n - 1) / 2 +
         calc(c, (a * n + b) % c, a % c, (a % c * n + b % c) / c);
}
long long a, b, p, q;
bool chk(long long l, long long r, long long L, long long R) {
  return calc(p, l * p + q - L, q, r - l + 1) >
         calc(p, l * p + q - R - 1, q, r - l + 1);
}
int T;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (cin >> T; T-- > 0;) {
    cin >> a >> b >> p >> q;
    long long l = 0, r = q / 2;
    while (l != r) {
      long long mid = (l + r) / 2;
      if (chk(a, b, q / 2 - mid, (q + 1) / 2 + mid))
        r = mid;
      else
        l = mid + 1;
    }
    long long tmp = l;
    l = a;
    r = b;
    while (l != r) {
      long long mid = (l + r) / 2;
      if (chk(a, mid, q / 2 - tmp, (q + 1) / 2 + tmp))
        r = mid;
      else
        l = mid + 1;
    }
    cout << l << '\n';
  }
  return 0;
}
