#include <bits/stdc++.h>
const int N = 100005;
const long long inf = 2e9;
long long a, b, p, q;
struct data {
  int x;
  long long val;
} f[N];
bool cmp(data a, data b) {
  return a.val < b.val || a.val == b.val && a.x < b.x;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    int L = sqrt(b - a + 1);
    long long ans = inf;
    int ansx;
    for (int i = 0; i < L; i++)
      f[i + 1].val = 2 * p * (a + i) % (q * 2), f[i + 1].x = a + i;
    std::sort(f + 1, f + L + 1, cmp);
    for (int i = 2; i <= L; i++)
      if (f[i].val == f[i - 1].val) f[i].x = f[i - 1].x;
    f[L + 1] = f[1];
    f[L + 1].val += q * 2;
    f[0] = f[L];
    long long k = 0;
    for (int i = 0; (i + 1) * L <= b - a + 1; i++) {
      long long tar = (q * 3 - k) % (q * 2);
      int lef = 1, rig = L;
      while (lef <= rig) {
        int mid = (lef + rig) / 2;
        if (f[mid].val <= tar)
          lef = mid + 1;
        else
          rig = mid - 1;
      }
      long long w = std::min((f[lef - 1].val + q * 2 - tar) % (q * 2),
                             (tar - f[lef - 1].val + q * 2) % (q * 2));
      if (w < ans || w == ans && f[lef - 1].x + L * i < ansx)
        ans = w, ansx = f[lef - 1].x + L * i;
      w = std::min((f[lef].val + q * 2 - tar) % (q * 2),
                   (tar - f[lef].val + q * 2) % (q * 2));
      if (w < ans || w == ans && f[lef].x + L * i < ansx)
        ans = w, ansx = f[lef].x + L * i;
      k = (k + (long long)2 * p * L) % (q * 2);
    }
    for (int i = b - L + 1; i <= b; i++) {
      long long w =
          std::min(((long long)2 * p * i + q) % (q * 2),
                   (q * 3 - (long long)2 * p * i % (q * 2)) % (q * 2));
      if (w < ans) ans = w, ansx = i;
    }
    printf("%d\n", ansx);
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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>
const int N = 100005;
const long long inf = 2e9;
long long a, b, p, q;
struct data {
  int x;
  long long val;
} f[N];
bool cmp(data a, data b) {
  return a.val < b.val || a.val == b.val && a.x < b.x;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    int L = sqrt(b - a + 1);
    long long ans = inf;
    int ansx;
    for (int i = 0; i < L; i++)
      f[i + 1].val = 2 * p * (a + i) % (q * 2), f[i + 1].x = a + i;
    std::sort(f + 1, f + L + 1, cmp);
    for (int i = 2; i <= L; i++)
      if (f[i].val == f[i - 1].val) f[i].x = f[i - 1].x;
    f[L + 1] = f[1];
    f[L + 1].val += q * 2;
    f[0] = f[L];
    long long k = 0;
    for (int i = 0; (i + 1) * L <= b - a + 1; i++) {
      long long tar = (q * 3 - k) % (q * 2);
      int lef = 1, rig = L;
      while (lef <= rig) {
        int mid = (lef + rig) / 2;
        if (f[mid].val <= tar)
          lef = mid + 1;
        else
          rig = mid - 1;
      }
      long long w = std::min((f[lef - 1].val + q * 2 - tar) % (q * 2),
                             (tar - f[lef - 1].val + q * 2) % (q * 2));
      if (w < ans || w == ans && f[lef - 1].x + L * i < ansx)
        ans = w, ansx = f[lef - 1].x + L * i;
      w = std::min((f[lef].val + q * 2 - tar) % (q * 2),
                   (tar - f[lef].val + q * 2) % (q * 2));
      if (w < ans || w == ans && f[lef].x + L * i < ansx)
        ans = w, ansx = f[lef].x + L * i;
      k = (k + (long long)2 * p * L) % (q * 2);
    }
    for (int i = b - L + 1; i <= b; i++) {
      long long w =
          std::min(((long long)2 * p * i + q) % (q * 2),
                   (q * 3 - (long long)2 * p * i % (q * 2)) % (q * 2));
      if (w < ans) ans = w, ansx = i;
    }
    printf("%d\n", ansx);
  }
  return 0;
}

```