#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v;
int a, b, p, q, sz, cls = 0;
inline int f(int x) {
  if ((long long)2 * p * x % (2 * q) <= q) {
    return q - (long long)2 * p * x % (2 * q);
  } else
    return (long long)2 * p * x % (2 * q) - q;
}
int main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> a >> b >> p >> q;
    cls = a;
    sz = sqrt(b - a + 1);
    for (int i = a; i < a + sz; i++) {
      v.push_back({(long long)2 * p * i % (2 * q), i});
    }
    sort(v.begin(), v.end());
    vector<pair<int, int> > tp;
    for (int i = 0; i < v.size(); i++) {
      if (tp.size() == 0 || tp.back().first != v[i].first) {
        tp.push_back({v[i].first, v[i].second});
      }
    }
    v = tp;
    int i;
    for (i = 0; i + sz - 1 <= b - a; i += sz) {
      int it =
          (upper_bound(
               v.begin(), v.end(),
               make_pair((int)(((q - (long long)2 * p * i) % (2 * q) + 2 * q) %
                               (2 * q)),
                         10000000)) -
           v.begin()) %
          v.size();
      for (int j = -1; j < 1; j++) {
        if (f(v[(v.size() + j + it) % v.size()].second + i) < f(cls)) {
          cls = v[(v.size() + j + it) % v.size()].second + i;
        } else if (f(v[(v.size() + j + it) % v.size()].second + i) == f(cls) &&
                   v[(v.size() + j + it) % v.size()].second + i < cls) {
          cls = v[(v.size() + j + it) % v.size()].second + i;
        }
      }
    }
    for (i += a; i <= b; i++) {
      if (f(i) < f(cls)) {
        cls = i;
      }
    }
    cout << cls << "\n";
    v.clear();
  }
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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;
vector<pair<int, int> > v;
int a, b, p, q, sz, cls = 0;
inline int f(int x) {
  if ((long long)2 * p * x % (2 * q) <= q) {
    return q - (long long)2 * p * x % (2 * q);
  } else
    return (long long)2 * p * x % (2 * q) - q;
}
int main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> a >> b >> p >> q;
    cls = a;
    sz = sqrt(b - a + 1);
    for (int i = a; i < a + sz; i++) {
      v.push_back({(long long)2 * p * i % (2 * q), i});
    }
    sort(v.begin(), v.end());
    vector<pair<int, int> > tp;
    for (int i = 0; i < v.size(); i++) {
      if (tp.size() == 0 || tp.back().first != v[i].first) {
        tp.push_back({v[i].first, v[i].second});
      }
    }
    v = tp;
    int i;
    for (i = 0; i + sz - 1 <= b - a; i += sz) {
      int it =
          (upper_bound(
               v.begin(), v.end(),
               make_pair((int)(((q - (long long)2 * p * i) % (2 * q) + 2 * q) %
                               (2 * q)),
                         10000000)) -
           v.begin()) %
          v.size();
      for (int j = -1; j < 1; j++) {
        if (f(v[(v.size() + j + it) % v.size()].second + i) < f(cls)) {
          cls = v[(v.size() + j + it) % v.size()].second + i;
        } else if (f(v[(v.size() + j + it) % v.size()].second + i) == f(cls) &&
                   v[(v.size() + j + it) % v.size()].second + i < cls) {
          cls = v[(v.size() + j + it) % v.size()].second + i;
        }
      }
    }
    for (i += a; i <= b; i++) {
      if (f(i) < f(cls)) {
        cls = i;
      }
    }
    cout << cls << "\n";
    v.clear();
  }
  return 0;
}

```