#include <bits/stdc++.h>
using namespace std;
pair<int, int> val[32000];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int a, b, p, q;
    scanf("%d%d%d%d", &a, &b, &p, &q);
    int n = (int)sqrt(b - a + 1), m = 1;
    for (int i = 0; i < n; i++) {
      val[i + 1].first = 2LL * (a + i) * p % (q * 2);
      val[i + 1].second = i;
    }
    sort(val + 1, val + n + 1);
    for (int i = 2; i <= n; i++)
      if (val[i].first != val[m].first) val[++m] = val[i];
    val[0] = val[m], val[0].first -= q * 2;
    val[m + 1] = val[1], val[m + 1].first += q * 2;
    pair<int, int> s(q * 2, 0);
    for (int i = 0; i < n; i++) {
      int fix = ((long long)(q * 2 - 2) * p % (q * 2) * i * n + q) % (q * 2),
          x = lower_bound(val + 1, val + m + 1, make_pair(fix, 0)) - val - 1;
      s = min(s, make_pair(abs(val[x].first - fix), val[x].second + a + n * i));
      s = min(s, make_pair(abs(val[x + 1].first - fix),
                           val[x + 1].second + a + n * i));
    }
    for (int i = a + n * n; i <= b; i++)
      s = min(s, make_pair((int)abs(2LL * i * p % (q * 2) - q), i));
    printf("%d\n", s.second);
  }
  return 0;
}

### Prompt

Please create a solution in cpp 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;
pair<int, int> val[32000];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int a, b, p, q;
    scanf("%d%d%d%d", &a, &b, &p, &q);
    int n = (int)sqrt(b - a + 1), m = 1;
    for (int i = 0; i < n; i++) {
      val[i + 1].first = 2LL * (a + i) * p % (q * 2);
      val[i + 1].second = i;
    }
    sort(val + 1, val + n + 1);
    for (int i = 2; i <= n; i++)
      if (val[i].first != val[m].first) val[++m] = val[i];
    val[0] = val[m], val[0].first -= q * 2;
    val[m + 1] = val[1], val[m + 1].first += q * 2;
    pair<int, int> s(q * 2, 0);
    for (int i = 0; i < n; i++) {
      int fix = ((long long)(q * 2 - 2) * p % (q * 2) * i * n + q) % (q * 2),
          x = lower_bound(val + 1, val + m + 1, make_pair(fix, 0)) - val - 1;
      s = min(s, make_pair(abs(val[x].first - fix), val[x].second + a + n * i));
      s = min(s, make_pair(abs(val[x + 1].first - fix),
                           val[x + 1].second + a + n * i));
    }
    for (int i = a + n * n; i <= b; i++)
      s = min(s, make_pair((int)abs(2LL * i * p % (q * 2) - q), i));
    printf("%d\n", s.second);
  }
  return 0;
}

```