#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long inf = 2e18;
const long long NN = 1e5 + 2;
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
long long q;
void set_values(vector<pair<long long, long long> >& v, long long idx,
                long long& min_diff, long long& ans, long long add1,
                long long add2) {
  long long y = abs(q - ((add1 + v[idx].first) % (q << 1)));
  if (min_diff > y) {
    min_diff = abs(q - ((add1 + v[idx].first) % (q << 1)));
    ans = v[idx].second + add2;
  }
  if (min_diff == y and v[idx].second + add2 < ans) {
    ans = v[idx].second + add2;
  }
  if (idx > 0) {
    idx--;
    y = abs(q - ((add1 + v[idx].first) % (q << 1)));
    if (min_diff > y) {
      min_diff = y;
      ans = v[idx].second + add2;
    }
    if (min_diff == y and v[idx].second + add2 < ans) {
      ans = v[idx].second + add2;
    }
  }
}
void solve() {
  long long p, a, b;
  cin >> a >> b >> p >> q;
  p <<= 1;
  vector<pair<long long, long long> > v;
  long long s = max(sqrt(b - a + 1), 4.0);
  set<long long> found;
  for (long long x = a; x < min(a + s, b + 1); x++) {
    if (found.find(p * x % (q << 1)) == found.end()) {
      v.emplace_back(p * x % (q << 1), x);
      found.emplace(p * x % (q << 1));
    }
  }
  sort(v.begin(), v.end());
  long long min_diff = inf, ans = inf;
  long long idx =
      lower_bound(v.begin(), v.end(), pair<long long, long long>(q, -1)) -
      v.begin();
  if (idx == int32_t(v.size())) idx--;
  set_values(v, idx, min_diff, ans, 0, 0);
  ;
  long long m;
  for (m = s; m + s + a < b; m += s) {
    long long add = m * p % (q << 1);
    idx = lower_bound(v.begin(), v.end(),
                      pair<long long, long long>(3 * q - add, -1)) -
          v.begin();
    if (idx == int32_t(v.size())) idx--;
    set_values(v, idx, min_diff, ans, add, m);
    idx = lower_bound(v.begin(), v.end(),
                      pair<long long, long long>(q - add, -1)) -
          v.begin();
    if (idx == int32_t(v.size())) idx--;
    set_values(v, idx, min_diff, ans, add, m);
    ;
  }
  for (m = a + m; m <= b; m++) {
    long long h = m * p % (q << 1);
    if (abs(h - q) < min_diff) {
      min_diff = abs(h - q);
      ans = m;
    }
  };
  cout << ans << '\n';
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long T = 1, tc;
  cin >> T;
  for (tc = 1; tc <= T; tc++) {
    solve();
  }
  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;
const long long mod = 1e9 + 7;
const long long inf = 2e18;
const long long NN = 1e5 + 2;
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
long long q;
void set_values(vector<pair<long long, long long> >& v, long long idx,
                long long& min_diff, long long& ans, long long add1,
                long long add2) {
  long long y = abs(q - ((add1 + v[idx].first) % (q << 1)));
  if (min_diff > y) {
    min_diff = abs(q - ((add1 + v[idx].first) % (q << 1)));
    ans = v[idx].second + add2;
  }
  if (min_diff == y and v[idx].second + add2 < ans) {
    ans = v[idx].second + add2;
  }
  if (idx > 0) {
    idx--;
    y = abs(q - ((add1 + v[idx].first) % (q << 1)));
    if (min_diff > y) {
      min_diff = y;
      ans = v[idx].second + add2;
    }
    if (min_diff == y and v[idx].second + add2 < ans) {
      ans = v[idx].second + add2;
    }
  }
}
void solve() {
  long long p, a, b;
  cin >> a >> b >> p >> q;
  p <<= 1;
  vector<pair<long long, long long> > v;
  long long s = max(sqrt(b - a + 1), 4.0);
  set<long long> found;
  for (long long x = a; x < min(a + s, b + 1); x++) {
    if (found.find(p * x % (q << 1)) == found.end()) {
      v.emplace_back(p * x % (q << 1), x);
      found.emplace(p * x % (q << 1));
    }
  }
  sort(v.begin(), v.end());
  long long min_diff = inf, ans = inf;
  long long idx =
      lower_bound(v.begin(), v.end(), pair<long long, long long>(q, -1)) -
      v.begin();
  if (idx == int32_t(v.size())) idx--;
  set_values(v, idx, min_diff, ans, 0, 0);
  ;
  long long m;
  for (m = s; m + s + a < b; m += s) {
    long long add = m * p % (q << 1);
    idx = lower_bound(v.begin(), v.end(),
                      pair<long long, long long>(3 * q - add, -1)) -
          v.begin();
    if (idx == int32_t(v.size())) idx--;
    set_values(v, idx, min_diff, ans, add, m);
    idx = lower_bound(v.begin(), v.end(),
                      pair<long long, long long>(q - add, -1)) -
          v.begin();
    if (idx == int32_t(v.size())) idx--;
    set_values(v, idx, min_diff, ans, add, m);
    ;
  }
  for (m = a + m; m <= b; m++) {
    long long h = m * p % (q << 1);
    if (abs(h - q) < min_diff) {
      min_diff = abs(h - q);
      ans = m;
    }
  };
  cout << ans << '\n';
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long T = 1, tc;
  cin >> T;
  for (tc = 1; tc <= T; tc++) {
    solve();
  }
  return 0;
}

```