#include <bits/stdc++.h>
using namespace std;
seed_seq seq{
    (uint64_t)chrono::duration_cast<chrono::nanoseconds>(
        chrono::high_resolution_clock::now().time_since_epoch())
        .count(),
};
mt19937 rng(seq);
int t;
long long a, b, p, q, dist, first, f, s;
long long md(long long first) {
  first %= (2ll * q);
  if (first < 0) first += 2ll * q;
  return first;
}
long long dt(long long first) { return min(first, 2ll * q - first); }
vector<pair<long long, long long> > u, v, w;
int32_t main() {
  ios_base ::sync_with_stdio(0);
  cin.tie();
  cout.tie();
  cin >> t;
  while (t--) {
    cin >> a >> b >> p >> q;
    dist = 1000000000000000005, first = -1;
    s = sqrt(b - a);
    f = md(q - 2ll * p * a);
    for (long long i = b - a; i >= s * s; i--) {
      if (dt(md(2ll * p * i - f)) <= dist)
        dist = dt(md(2ll * p * i - f)), first = i;
    }
    u.clear();
    v.clear();
    for (int i = 0; i < s; i++) {
      u.push_back({md(2ll * p * s * i), i});
      v.push_back({md(2ll * p * i), i});
    }
    sort(v.begin(), v.end());
    w.clear();
    for (int i = 0; i < s; i++) {
      if (i == 0 || v[i].first != v[i - 1].first) w.push_back(v[i]);
    }
    v = w;
    for (pair<long long, long long> i : u) {
      long long d = md(f - i.first);
      int l = 0, r = s - 1;
      while (l != r) {
        int mid = (l + r + 1) / 2;
        if (v[mid].first <= d)
          l = mid;
        else
          r = mid - 1;
      }
      r = (l + 1) % s;
      if (dt(md(v[l].first - d)) < dist)
        dist = dt(md(v[l].first - d)), first = v[l].second + i.second * s;
      else if (dt(md(v[l].first - d)) == dist &&
               v[l].second + i.second * s < first)
        first = v[l].second + i.second * s;
      if (dt(md(v[r].first - d)) < dist)
        dist = dt(md(v[r].first - d)), first = v[r].second + i.second * s;
      else if (dt(md(v[r].first - d)) == dist &&
               v[r].second + i.second * s < first)
        first = v[r].second + i.second * s;
    }
    cout << first + a << '\n';
  }
}

### Prompt

In Cpp, your task is to solve 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;
seed_seq seq{
    (uint64_t)chrono::duration_cast<chrono::nanoseconds>(
        chrono::high_resolution_clock::now().time_since_epoch())
        .count(),
};
mt19937 rng(seq);
int t;
long long a, b, p, q, dist, first, f, s;
long long md(long long first) {
  first %= (2ll * q);
  if (first < 0) first += 2ll * q;
  return first;
}
long long dt(long long first) { return min(first, 2ll * q - first); }
vector<pair<long long, long long> > u, v, w;
int32_t main() {
  ios_base ::sync_with_stdio(0);
  cin.tie();
  cout.tie();
  cin >> t;
  while (t--) {
    cin >> a >> b >> p >> q;
    dist = 1000000000000000005, first = -1;
    s = sqrt(b - a);
    f = md(q - 2ll * p * a);
    for (long long i = b - a; i >= s * s; i--) {
      if (dt(md(2ll * p * i - f)) <= dist)
        dist = dt(md(2ll * p * i - f)), first = i;
    }
    u.clear();
    v.clear();
    for (int i = 0; i < s; i++) {
      u.push_back({md(2ll * p * s * i), i});
      v.push_back({md(2ll * p * i), i});
    }
    sort(v.begin(), v.end());
    w.clear();
    for (int i = 0; i < s; i++) {
      if (i == 0 || v[i].first != v[i - 1].first) w.push_back(v[i]);
    }
    v = w;
    for (pair<long long, long long> i : u) {
      long long d = md(f - i.first);
      int l = 0, r = s - 1;
      while (l != r) {
        int mid = (l + r + 1) / 2;
        if (v[mid].first <= d)
          l = mid;
        else
          r = mid - 1;
      }
      r = (l + 1) % s;
      if (dt(md(v[l].first - d)) < dist)
        dist = dt(md(v[l].first - d)), first = v[l].second + i.second * s;
      else if (dt(md(v[l].first - d)) == dist &&
               v[l].second + i.second * s < first)
        first = v[l].second + i.second * s;
      if (dt(md(v[r].first - d)) < dist)
        dist = dt(md(v[r].first - d)), first = v[r].second + i.second * s;
      else if (dt(md(v[r].first - d)) == dist &&
               v[r].second + i.second * s < first)
        first = v[r].second + i.second * s;
    }
    cout << first + a << '\n';
  }
}

```