#include <bits/stdc++.h>
using namespace std;
template <typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) {
  return os << '(' << pai.first << ' ' << pai.second << ')';
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
  cout << '[';
  for (int i = 0, _i = (((int)(v).size())); i < _i; i++) cout << v[i] << ",";
  cout << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T>
void get_max(T &a, T b) {
  a = max(a, b);
}
template <typename T>
void get_min(T &a, T b) {
  a = min(a, b);
}
int a, b, p, q;
int solve() {
  cin >> a >> b >> p >> q;
  int interval;
  for (interval = 0; interval * interval < b - a + 1; interval++)
    ;
  vector<pair<int, int> > cand;
  for (int i = 0, _i = (interval); i < _i; i++)
    cand.push_back({2LL * p * i % (2 * q), i});
  sort((cand).begin(), (cand).end());
  unique((cand).begin(), (cand).end(),
         [](pair<int, int> a, pair<int, int> b) { return a.first == b.first; });
  0;
  int bun;
  pair<int, int> res = {(1 << 30), 0};
  for (bun = 0; (bun + 1) * interval <= b - a + 1; bun++) {
    0;
    int tf =
        (q + 1LL * (2 * q - 2) * p % (2 * q) * (a + bun * interval)) % (2 * q);
    auto p =
        lower_bound((cand).begin(), (cand).end(), make_pair(tf, (1 << 30)));
    if (p == cand.end()) p = cand.begin();
    for (int j = 0, _j = (2); j < _j; j++) {
      0;
      get_min(res, {min(abs(tf - p->first + (long long)20 * q) % (2 * q),
                        abs(p->first - tf + (long long)20 * q) % (2 * q)),
                    a + bun * interval + p->second});
      if (p == cand.begin())
        p = prev(cand.end());
      else
        p = prev(p);
    }
  }
  0;
  for (int i = (bun * interval + a), _i = (b + 1); i < _i; i++) {
    get_min(res, {min((q + (long long)(q * 2 - 2) * p % (2 * q) * i) % (2 * q),
                      (q + 2LL * p % (2 * q) * i) % (2 * q)),
                  i});
    0;
  }
  0;
  0;
  return res.second;
}
int main(void) {
  iostream::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int T;
  cin >> T;
  for (int i = 0, _i = (T); i < _i; i++) cout << solve() << '\n';
}

### 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>
using namespace std;
template <typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) {
  return os << '(' << pai.first << ' ' << pai.second << ')';
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
  cout << '[';
  for (int i = 0, _i = (((int)(v).size())); i < _i; i++) cout << v[i] << ",";
  cout << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
  cout << "{";
  for (auto p : v) cout << p << ",";
  cout << "}";
  return os;
}
template <typename T>
void get_max(T &a, T b) {
  a = max(a, b);
}
template <typename T>
void get_min(T &a, T b) {
  a = min(a, b);
}
int a, b, p, q;
int solve() {
  cin >> a >> b >> p >> q;
  int interval;
  for (interval = 0; interval * interval < b - a + 1; interval++)
    ;
  vector<pair<int, int> > cand;
  for (int i = 0, _i = (interval); i < _i; i++)
    cand.push_back({2LL * p * i % (2 * q), i});
  sort((cand).begin(), (cand).end());
  unique((cand).begin(), (cand).end(),
         [](pair<int, int> a, pair<int, int> b) { return a.first == b.first; });
  0;
  int bun;
  pair<int, int> res = {(1 << 30), 0};
  for (bun = 0; (bun + 1) * interval <= b - a + 1; bun++) {
    0;
    int tf =
        (q + 1LL * (2 * q - 2) * p % (2 * q) * (a + bun * interval)) % (2 * q);
    auto p =
        lower_bound((cand).begin(), (cand).end(), make_pair(tf, (1 << 30)));
    if (p == cand.end()) p = cand.begin();
    for (int j = 0, _j = (2); j < _j; j++) {
      0;
      get_min(res, {min(abs(tf - p->first + (long long)20 * q) % (2 * q),
                        abs(p->first - tf + (long long)20 * q) % (2 * q)),
                    a + bun * interval + p->second});
      if (p == cand.begin())
        p = prev(cand.end());
      else
        p = prev(p);
    }
  }
  0;
  for (int i = (bun * interval + a), _i = (b + 1); i < _i; i++) {
    get_min(res, {min((q + (long long)(q * 2 - 2) * p % (2 * q) * i) % (2 * q),
                      (q + 2LL * p % (2 * q) * i) % (2 * q)),
                  i});
    0;
  }
  0;
  0;
  return res.second;
}
int main(void) {
  iostream::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int T;
  cin >> T;
  for (int i = 0, _i = (T); i < _i; i++) cout << solve() << '\n';
}

```