#include <bits/stdc++.h>
struct st {
  long long data, rem;
  st(long long d = 0, long long r = 0) : data(d), rem(r) {}
  bool operator<(const st& rhs) const {
    if (rem != rhs.rem) {
      return rem < rhs.rem;
    }
    return data < rhs.data;
  }
} d[100005];
inline long long slove(long long a, long long b, long long p, long long q) {
  p *= 2;
  q *= 2;
  long long siz = (long long)sqrt((double)(b - a + 1) + 0.5);
  for (int i = 0; i < siz; ++i) {
    d[i] = st(a + i, (a + i) * p % q);
  }
  std::sort(d, d + siz);
  int idx = 1;
  for (int i = 1; i < siz; ++i) {
    if (d[i].rem != d[i - 1].rem) {
      d[idx++] = d[i];
    }
  }
  d[idx++] = d[0];
  d[idx - 1].rem += q;
  long long xpt;
  int left, right, mid;
  long long mn_data, mn_rem = 66666666666666666LL;
  ;
  long long trem, tdata;
  int i;
  for (i = 0; siz * (i + 1) + a - 1 <= b; ++i) {
    xpt = ((q / 2 - siz * i % q * p % q) % q + q) % q;
    left = 0;
    right = idx;
    while (left != right) {
      mid = (left + right) / 2;
      if (d[mid].rem < xpt) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    if (left == 0) {
      trem = p * (i * siz % q + d[left].data) % q;
      tdata = i * siz + d[left].data;
    } else if (left == idx) {
      trem = p * (i * siz % q + d[left - 1].data) % q;
      tdata = i * siz + d[left - 1].data;
    } else {
      if (d[left].rem - xpt < xpt - d[left - 1].rem) {
        trem = p * (i * siz % q + d[left].data) % q;
        tdata = i * siz + d[left].data;
      } else if (d[left].rem - xpt > xpt - d[left - 1].rem) {
        trem = p * (i * siz % q + d[left - 1].data) % q;
        tdata = i * siz + d[left - 1].data;
      } else if (d[left].data < d[left - 1].data) {
        trem = p * (i * siz % q + d[left].data) % q;
        tdata = i * siz + d[left].data;
      } else {
        trem = p * (i * siz % q + d[left - 1].data) % q;
        tdata = i * siz + d[left - 1].data;
      }
    }
    if (std::abs(mn_rem - q / 2) > std::abs(trem - q / 2)) {
      mn_rem = trem;
      mn_data = tdata;
    }
    xpt += q;
    left = 0;
    right = idx;
    while (left != right) {
      mid = (left + right) / 2;
      if (d[mid].rem < xpt) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    if (left == 0) {
      trem = p * (i * siz % q + d[left].data) % q;
      tdata = i * siz + d[left].data;
    } else if (left == idx) {
      trem = p * (i * siz % q + d[left - 1].data) % q;
      tdata = i * siz + d[left - 1].data;
    } else {
      if (d[left].rem - xpt < xpt - d[left - 1].rem) {
        trem = p * (i * siz % q + d[left].data) % q;
        tdata = i * siz + d[left].data;
      } else if (d[left].rem - xpt > xpt - d[left - 1].rem) {
        trem = p * (i * siz % q + d[left - 1].data) % q;
        tdata = i * siz + d[left - 1].data;
      } else if (d[left].data < d[left - 1].data) {
        trem = p * (i * siz % q + d[left].data) % q;
        tdata = i * siz + d[left].data;
      } else {
        trem = p * (i * siz % q + d[left - 1].data) % q;
        tdata = i * siz + d[left - 1].data;
      }
    }
    if (std::abs(mn_rem - q / 2) > std::abs(trem - q / 2)) {
      mn_rem = trem;
      mn_data = tdata;
    }
  }
  for (long long x = siz * i + a; x <= b; ++x) {
    if (std::abs(mn_rem - q / 2) > std::abs(p * x % q - q / 2)) {
      mn_rem = p * x % q;
      mn_data = x;
    }
  }
  return mn_data;
}
int main() {
  int numkase;
  scanf("%d", &numkase);
  int a, b, p, q;
  while (numkase--) {
    scanf("%d%d%d%d", &a, &b, &p, &q);
    printf("%d\n", (int)slove(a, b, p, q));
  }
  return 0;
}

### Prompt

Your challenge is to write 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>
struct st {
  long long data, rem;
  st(long long d = 0, long long r = 0) : data(d), rem(r) {}
  bool operator<(const st& rhs) const {
    if (rem != rhs.rem) {
      return rem < rhs.rem;
    }
    return data < rhs.data;
  }
} d[100005];
inline long long slove(long long a, long long b, long long p, long long q) {
  p *= 2;
  q *= 2;
  long long siz = (long long)sqrt((double)(b - a + 1) + 0.5);
  for (int i = 0; i < siz; ++i) {
    d[i] = st(a + i, (a + i) * p % q);
  }
  std::sort(d, d + siz);
  int idx = 1;
  for (int i = 1; i < siz; ++i) {
    if (d[i].rem != d[i - 1].rem) {
      d[idx++] = d[i];
    }
  }
  d[idx++] = d[0];
  d[idx - 1].rem += q;
  long long xpt;
  int left, right, mid;
  long long mn_data, mn_rem = 66666666666666666LL;
  ;
  long long trem, tdata;
  int i;
  for (i = 0; siz * (i + 1) + a - 1 <= b; ++i) {
    xpt = ((q / 2 - siz * i % q * p % q) % q + q) % q;
    left = 0;
    right = idx;
    while (left != right) {
      mid = (left + right) / 2;
      if (d[mid].rem < xpt) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    if (left == 0) {
      trem = p * (i * siz % q + d[left].data) % q;
      tdata = i * siz + d[left].data;
    } else if (left == idx) {
      trem = p * (i * siz % q + d[left - 1].data) % q;
      tdata = i * siz + d[left - 1].data;
    } else {
      if (d[left].rem - xpt < xpt - d[left - 1].rem) {
        trem = p * (i * siz % q + d[left].data) % q;
        tdata = i * siz + d[left].data;
      } else if (d[left].rem - xpt > xpt - d[left - 1].rem) {
        trem = p * (i * siz % q + d[left - 1].data) % q;
        tdata = i * siz + d[left - 1].data;
      } else if (d[left].data < d[left - 1].data) {
        trem = p * (i * siz % q + d[left].data) % q;
        tdata = i * siz + d[left].data;
      } else {
        trem = p * (i * siz % q + d[left - 1].data) % q;
        tdata = i * siz + d[left - 1].data;
      }
    }
    if (std::abs(mn_rem - q / 2) > std::abs(trem - q / 2)) {
      mn_rem = trem;
      mn_data = tdata;
    }
    xpt += q;
    left = 0;
    right = idx;
    while (left != right) {
      mid = (left + right) / 2;
      if (d[mid].rem < xpt) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    if (left == 0) {
      trem = p * (i * siz % q + d[left].data) % q;
      tdata = i * siz + d[left].data;
    } else if (left == idx) {
      trem = p * (i * siz % q + d[left - 1].data) % q;
      tdata = i * siz + d[left - 1].data;
    } else {
      if (d[left].rem - xpt < xpt - d[left - 1].rem) {
        trem = p * (i * siz % q + d[left].data) % q;
        tdata = i * siz + d[left].data;
      } else if (d[left].rem - xpt > xpt - d[left - 1].rem) {
        trem = p * (i * siz % q + d[left - 1].data) % q;
        tdata = i * siz + d[left - 1].data;
      } else if (d[left].data < d[left - 1].data) {
        trem = p * (i * siz % q + d[left].data) % q;
        tdata = i * siz + d[left].data;
      } else {
        trem = p * (i * siz % q + d[left - 1].data) % q;
        tdata = i * siz + d[left - 1].data;
      }
    }
    if (std::abs(mn_rem - q / 2) > std::abs(trem - q / 2)) {
      mn_rem = trem;
      mn_data = tdata;
    }
  }
  for (long long x = siz * i + a; x <= b; ++x) {
    if (std::abs(mn_rem - q / 2) > std::abs(p * x % q - q / 2)) {
      mn_rem = p * x % q;
      mn_data = x;
    }
  }
  return mn_data;
}
int main() {
  int numkase;
  scanf("%d", &numkase);
  int a, b, p, q;
  while (numkase--) {
    scanf("%d%d%d%d", &a, &b, &p, &q);
    printf("%d\n", (int)slove(a, b, p, q));
  }
  return 0;
}

```