#include <bits/stdc++.h>
unsigned T, a, b, P, Q, Org_S, S, Mod;
struct Ad {
  unsigned x, v;
  inline bool operator==(const Ad &c) const { return v == c.v; }
  inline bool operator<(const Ad &c) const { return v < c.v; }
} A[35005], Ans;
inline void Mo(unsigned &x) {
  if (x >= Mod) x -= Mod;
}
inline unsigned Yu(unsigned x) { return x < Mod ? x : x - Mod; }
inline void Upd(unsigned x, unsigned v) {
  if (v < Ans.v || (v == Ans.v && x < Ans.x)) Ans = (Ad){x, v};
}
inline unsigned Min(unsigned x, unsigned y) { return x < y ? x : y; }
inline void Solve() {
  scanf("%u%u%u%u", &a, &b, &P, &Q), Org_S = S = ceil(sqrt((++b) - a)),
                                     (P <<= 1) %= (Mod = Q << 1);
  for (unsigned i = 0; i < S; ++i)
    A[i] = (Ad){i, i ? Yu(A[i - 1].v + P)
                     : (unsigned)((unsigned long long)P * a % Mod)};
  std::stable_sort(A, A + S), S = std::unique(A, A + S) - A, Ans.v = Mod;
  unsigned now = a, Det = Mod - (unsigned long long)P * Org_S % Mod;
  for (unsigned pos, nxt; now + Org_S <= b; now += Org_S, Mo(Q += Det)) {
    nxt = pos = std::upper_bound(A, A + S, (Ad){0, Q}) - A;
    if (nxt == S) nxt = 0;
    if (pos)
      --pos;
    else
      pos = S - 1;
    Upd(now + A[nxt].x, Min(Yu(A[nxt].v + Mod - Q), Yu(Mod + Q - A[nxt].v))),
        Upd(now + A[pos].x,
            Min(Yu(A[pos].v + Mod - Q), Yu(Mod + Q - A[pos].v)));
  }
  for (unsigned k = (unsigned long long)P * a % Mod; now < b; ++now, Mo(k += P))
    Upd(now, Min(Yu(k + Mod - Q), Yu(Mod + Q - k)));
  printf("%u\n", Ans.x);
}
int main() {
  for (scanf("%u", &T); T--; Solve())
    ;
  return 0;
}
