#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
inline int read() {
  int sum = 0, p = 1;
  char ch = getchar();
  while (!(('0' <= ch && ch <= '9') || ch == '-')) ch = getchar();
  if (ch == '-') p = -1, ch = getchar();
  while ('0' <= ch && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum * p;
}
const long long maxn = 2e5 + 20;
long long a, b, p, q, len;
struct node {
  long long pos, id;
};
node x[maxn], y[maxn];
inline bool cmp(node a, node b) {
  return a.pos == b.pos ? a.id < b.id : a.pos < b.pos;
}
inline void init() {
  a = read();
  b = read();
  p = read() << 1;
  q = read() << 1;
  len = b - a + 1;
  long long ad = (long long)p * a % q, S = sqrt(len), q2 = q >> 1;
  p %= q;
  long long ans = q + 1, ansid = 0;
  for (long long i = (0), _end_ = (S - 1); i <= _end_; i++)
    x[i].id = i, x[i].pos = ((long long)i * p + ad) % q;
  for (long long i = (0), _end_ = (S - 1); i <= _end_; i++)
    y[i].id = i * S, y[i].pos = (long long)i * S * p % q;
  sort(x, x + S, cmp);
  long long ys = 0;
  sort(y, y + S, cmp);
  for (long long i = (1), _end_ = (S - 1); i <= _end_; i++)
    if (y[i].pos == y[ys].pos)
      ;
    else
      y[++ys] = y[i];
  ys++;
  reverse(y, y + ys);
  long long j = 0;
  for (long long i = (0), _end_ = (S - 1); i <= _end_; i++) {
    while (j < ys && x[i].pos + y[j].pos > q2) j++;
    if (j < ys) {
      long long t = q2 - (x[i].pos + y[j].pos), ID = x[i].id + y[j].id;
      if (t < ans || (t == ans && ansid > ID)) ans = t, ansid = ID;
    }
    if (j) {
      long long J = j - 1;
      long long t = x[i].pos + y[J].pos - q2, ID = x[i].id + y[J].id;
      if (t < ans || (t == ans && ansid > ID)) ans = t, ansid = ID;
    }
  }
  j = 0;
  for (long long i = (0), _end_ = (S - 1); i <= _end_; i++) {
    while (j < ys && x[i].pos + y[j].pos > q2 + q) j++;
    if (j < ys && x[i].pos + y[j].pos >= q) {
      long long t = q2 + q - (x[i].pos + y[j].pos), ID = x[i].id + y[j].id;
      if (t < ans || (ans == t && ansid > ID)) ans = t, ansid = ID;
    }
    if (j) {
      long long J = j - 1;
      long long t = x[i].pos + y[J].pos - q2 - q, ID = x[i].id + y[J].id;
      if (t < 0) continue;
      if (t < ans || (ans == t && ansid > ID)) ans = t, ansid = ID;
    }
  }
  for (long long i = (S * S), _end_ = (len - 1); i <= _end_; i++) {
    long long t = ((long long)i * p + ad) % q;
    if (abs(q2 - t) < ans) ans = abs(q2 - t), ansid = i;
  }
  printf("%lld\n", ansid + a);
}
signed main() {
  long long t = read();
  while (t--) init();
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

You have given integers a, b, p, and q. Let f(x) = abs(sin(p/q π x)).

Find minimum possible integer x that maximizes f(x) where a ≤ x ≤ b.

Input

Each test contains multiple test cases. 

The first line contains the number of test cases t (1 ≤ t ≤ 100) — the number of test cases.

The first line of each test case contains four integers a, b, p, and q (0 ≤ a ≤ b ≤ 10^{9}, 1 ≤ p, q ≤ 10^{9}).

Output

Print the minimum possible integer x for each test cases, separated by newline.

Example

Input


2
0 3 1 3
17 86 389 995


Output


1
55

Note

In the first test case, f(0) = 0, f(1) = f(2) ≈ 0.866, f(3) = 0.

In the second test case, f(55) ≈ 0.999969, which is the largest among all possible values.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
inline int read() {
  int sum = 0, p = 1;
  char ch = getchar();
  while (!(('0' <= ch && ch <= '9') || ch == '-')) ch = getchar();
  if (ch == '-') p = -1, ch = getchar();
  while ('0' <= ch && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum * p;
}
const long long maxn = 2e5 + 20;
long long a, b, p, q, len;
struct node {
  long long pos, id;
};
node x[maxn], y[maxn];
inline bool cmp(node a, node b) {
  return a.pos == b.pos ? a.id < b.id : a.pos < b.pos;
}
inline void init() {
  a = read();
  b = read();
  p = read() << 1;
  q = read() << 1;
  len = b - a + 1;
  long long ad = (long long)p * a % q, S = sqrt(len), q2 = q >> 1;
  p %= q;
  long long ans = q + 1, ansid = 0;
  for (long long i = (0), _end_ = (S - 1); i <= _end_; i++)
    x[i].id = i, x[i].pos = ((long long)i * p + ad) % q;
  for (long long i = (0), _end_ = (S - 1); i <= _end_; i++)
    y[i].id = i * S, y[i].pos = (long long)i * S * p % q;
  sort(x, x + S, cmp);
  long long ys = 0;
  sort(y, y + S, cmp);
  for (long long i = (1), _end_ = (S - 1); i <= _end_; i++)
    if (y[i].pos == y[ys].pos)
      ;
    else
      y[++ys] = y[i];
  ys++;
  reverse(y, y + ys);
  long long j = 0;
  for (long long i = (0), _end_ = (S - 1); i <= _end_; i++) {
    while (j < ys && x[i].pos + y[j].pos > q2) j++;
    if (j < ys) {
      long long t = q2 - (x[i].pos + y[j].pos), ID = x[i].id + y[j].id;
      if (t < ans || (t == ans && ansid > ID)) ans = t, ansid = ID;
    }
    if (j) {
      long long J = j - 1;
      long long t = x[i].pos + y[J].pos - q2, ID = x[i].id + y[J].id;
      if (t < ans || (t == ans && ansid > ID)) ans = t, ansid = ID;
    }
  }
  j = 0;
  for (long long i = (0), _end_ = (S - 1); i <= _end_; i++) {
    while (j < ys && x[i].pos + y[j].pos > q2 + q) j++;
    if (j < ys && x[i].pos + y[j].pos >= q) {
      long long t = q2 + q - (x[i].pos + y[j].pos), ID = x[i].id + y[j].id;
      if (t < ans || (ans == t && ansid > ID)) ans = t, ansid = ID;
    }
    if (j) {
      long long J = j - 1;
      long long t = x[i].pos + y[J].pos - q2 - q, ID = x[i].id + y[J].id;
      if (t < 0) continue;
      if (t < ans || (ans == t && ansid > ID)) ans = t, ansid = ID;
    }
  }
  for (long long i = (S * S), _end_ = (len - 1); i <= _end_; i++) {
    long long t = ((long long)i * p + ad) % q;
    if (abs(q2 - t) < ans) ans = abs(q2 - t), ansid = i;
  }
  printf("%lld\n", ansid + a);
}
signed main() {
  long long t = read();
  while (t--) init();
  return 0;
}

```