#include <bits/stdc++.h>
using namespace std;
int a, b, p, q, p2, q2, len, cnt;
pair<long long, int> ans, may[40005];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d%d", &a, &b, &p, &q);
    p2 = p * 2, q2 = q * 2;
    len = sqrt(b - a + 1);
    cnt = 0;
    for (register int i = 0; i < len; i++) {
      may[++cnt] = make_pair(((long long)p2 * (a + i)) % q2, i);
    }
    sort(may + 1, may + 1 + cnt);
    cnt = 0;
    for (register int i = 1; i <= len; i++) {
      if (i == 1 || may[i].first != may[i - 1].first) {
        may[++cnt] = may[i];
      }
    }
    may[0] = may[cnt], may[cnt + 1] = may[1];
    int temp = (long long)p2 * len % q2;
    int now = 0, L = a, pos;
    ans = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
    for (register int i = 0; i < len;
         i++, now = ((long long)now + temp) % q2, L += len) {
      pos = lower_bound(may + 1, may + 1 + cnt,
                        make_pair(((long long)q - now + q2) % q2, 0)) -
            may - 1;
      ans = min(ans, make_pair(abs((may[pos].first + now) % q2 - q),
                               may[pos].second + L));
      ans = min(ans, make_pair(abs((may[pos + 1].first + now) % q2 - q),
                               may[pos + 1].second + L));
    }
    for (register int i = a + len * len; i <= b; i++) {
      ans = min(ans, make_pair(abs((long long)p2 * i % q2 - q), i));
    }
    printf("%d\n", ans.second);
  }
}
