#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <int n, class... T>
typename std::enable_if<(n >= sizeof...(T))>::type __output_tuple(
    std::ostream &, std::tuple<T...> const &) {}
template <int n, class... T>
typename std::enable_if<(n < sizeof...(T))>::type __output_tuple(
    std::ostream &os, std::tuple<T...> const &t) {
  os << (n == 0 ? "" : ", ") << std::get<n>(t);
  __output_tuple<n + 1>(os, t);
}
template <class... T>
std::ostream &operator<<(std::ostream &os, std::tuple<T...> const &t) {
  os << "(";
  __output_tuple<0>(os, t);
  os << ")";
  return os;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> const &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::stack<T> &a) {
  os << "{";
  for (auto tmp = a; tmp.size(); tmp.pop())
    os << (a.size() == tmp.size() ? "" : ", ") << tmp.top();
  os << "}";
  return os;
}
template <class T, class Container, class Compare>
std::ostream &operator<<(std::ostream &os,
                         std::priority_queue<T, Container, Compare> a) {
  os << "{ (top) ";
  while (a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <class T, class Container>
std::ostream &operator<<(std::ostream &os, std::queue<T, Container> a) {
  os << "{ ";
  while (a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <
    class T,
    class = typename std::iterator_traits<decltype(begin(T()))>::value_type,
    class = typename std::enable_if<!std::is_same<T, std::string>::value>::type>
std::ostream &operator<<(std::ostream &os, const T &a) {
  for (auto ite = begin(a); ite != end(a); ++ite)
    os << (ite == begin(a) ? "" : " ") << *ite;
  return os;
}
template <class X>
void myuniq(X &x) {
  auto u = x;
  int n = u.size();
  x.clear();
  for (int i = 0; i < n; i++) {
    if (i == 0 || u[i - 1].first != u[i].first) {
      x.push_back(u[i]);
    }
  }
}
int solve(int a, int b, int p, int q) {
  if (q == 1) return a;
  if (a == b) return a;
  int t = b - a;
  ll v = 0;
  while ((v + 1) * (v + 1) <= t) v++;
  v--;
  int qmid = (q + 1) / 2;
  auto getDist = [&](int val) {
    return q % 2 == 0 ? abs(qmid - val)
                      : min(abs(qmid - val), abs(qmid - 1 - val));
  };
  using Q = tuple<int, int, int>;
  Q best(q, 0, 0);
  if (v == 0) {
    for (int x = a; x <= b; x++) {
      best = min(best, Q(getDist((ll)p * x % q), x, 0));
    }
    return get<1>(best);
  }
  assert(v >= 1);
  using P = pair<int, int>;
  vector<pair<int, int>> X(v + 1), Y(v);
  for (int i = 0; i <= v; i++) X[i] = make_pair((ll)p * (a + i * v) % q, i);
  for (int i = 0; i <= v - 1; i++) Y[i] = make_pair((ll)p * i % q, i);
  sort(begin(X), end(X));
  sort(begin(Y), end(Y));
  myuniq(X);
  myuniq(Y);
  int y = 0;
  for (int x = 0; x <= v; x++) {
    int now_val = (X[x].first + Y[y].first) % q;
    while (1) {
      int next_y = y == 0 ? v - 1 : y - 1;
      int next_val = (X[x].first + Y[next_y].first) % q;
      if (getDist(next_val) < getDist(now_val)) {
        now_val = next_val;
        y = next_y;
      } else
        break;
    }
    while (1) {
      int next_y = y == v - 1 ? 0 : y + 1;
      int next_val = (X[x].first + Y[next_y].first) % q;
      if (getDist(next_val) < getDist(now_val)) {
        now_val = next_val;
        y = next_y;
      } else
        break;
    }
    best = min(best, Q(getDist(now_val), X[x].second, Y[y].second));
    {
      int ext_y = y == 0 ? v - 1 : y - 1;
      int ext_val = (X[x].first + Y[ext_y].first) % q;
      int ext_dist = getDist(ext_val);
      best = min(best, Q(ext_dist, X[x].second, Y[ext_y].second));
    }
    {
      int ext_y = y == v - 1 ? 0 : y + 1;
      int ext_val = (X[x].first + Y[ext_y].first) % q;
      int ext_dist = getDist(ext_val);
      best = min(best, Q(ext_dist, X[x].second, Y[ext_y].second));
    }
  }
  assert(v * v + v - 1 <= t);
  for (ll i = v * v + v; i <= t; i++) {
    int val = p * (a + i) % q;
    int dist = getDist(val);
    Q cand(dist, i / v, i % v);
    best = min(best, cand);
  }
  assert(get<0>(best) != q);
  return a + get<1>(best) * v + get<2>(best);
}
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int tim;
  cin >> tim;
  while (tim--) {
    int a, b, p, q;
    cin >> a >> b >> p >> q;
    int x = solve(a, b, p, q);
    assert(a <= x && x <= b);
    cout << solve(a, b, p, q) << "\n";
  }
  return 0;
}

### Prompt

Please formulate 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;
using ll = long long;
template <int n, class... T>
typename std::enable_if<(n >= sizeof...(T))>::type __output_tuple(
    std::ostream &, std::tuple<T...> const &) {}
template <int n, class... T>
typename std::enable_if<(n < sizeof...(T))>::type __output_tuple(
    std::ostream &os, std::tuple<T...> const &t) {
  os << (n == 0 ? "" : ", ") << std::get<n>(t);
  __output_tuple<n + 1>(os, t);
}
template <class... T>
std::ostream &operator<<(std::ostream &os, std::tuple<T...> const &t) {
  os << "(";
  __output_tuple<0>(os, t);
  os << ")";
  return os;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> const &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::stack<T> &a) {
  os << "{";
  for (auto tmp = a; tmp.size(); tmp.pop())
    os << (a.size() == tmp.size() ? "" : ", ") << tmp.top();
  os << "}";
  return os;
}
template <class T, class Container, class Compare>
std::ostream &operator<<(std::ostream &os,
                         std::priority_queue<T, Container, Compare> a) {
  os << "{ (top) ";
  while (a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <class T, class Container>
std::ostream &operator<<(std::ostream &os, std::queue<T, Container> a) {
  os << "{ ";
  while (a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <
    class T,
    class = typename std::iterator_traits<decltype(begin(T()))>::value_type,
    class = typename std::enable_if<!std::is_same<T, std::string>::value>::type>
std::ostream &operator<<(std::ostream &os, const T &a) {
  for (auto ite = begin(a); ite != end(a); ++ite)
    os << (ite == begin(a) ? "" : " ") << *ite;
  return os;
}
template <class X>
void myuniq(X &x) {
  auto u = x;
  int n = u.size();
  x.clear();
  for (int i = 0; i < n; i++) {
    if (i == 0 || u[i - 1].first != u[i].first) {
      x.push_back(u[i]);
    }
  }
}
int solve(int a, int b, int p, int q) {
  if (q == 1) return a;
  if (a == b) return a;
  int t = b - a;
  ll v = 0;
  while ((v + 1) * (v + 1) <= t) v++;
  v--;
  int qmid = (q + 1) / 2;
  auto getDist = [&](int val) {
    return q % 2 == 0 ? abs(qmid - val)
                      : min(abs(qmid - val), abs(qmid - 1 - val));
  };
  using Q = tuple<int, int, int>;
  Q best(q, 0, 0);
  if (v == 0) {
    for (int x = a; x <= b; x++) {
      best = min(best, Q(getDist((ll)p * x % q), x, 0));
    }
    return get<1>(best);
  }
  assert(v >= 1);
  using P = pair<int, int>;
  vector<pair<int, int>> X(v + 1), Y(v);
  for (int i = 0; i <= v; i++) X[i] = make_pair((ll)p * (a + i * v) % q, i);
  for (int i = 0; i <= v - 1; i++) Y[i] = make_pair((ll)p * i % q, i);
  sort(begin(X), end(X));
  sort(begin(Y), end(Y));
  myuniq(X);
  myuniq(Y);
  int y = 0;
  for (int x = 0; x <= v; x++) {
    int now_val = (X[x].first + Y[y].first) % q;
    while (1) {
      int next_y = y == 0 ? v - 1 : y - 1;
      int next_val = (X[x].first + Y[next_y].first) % q;
      if (getDist(next_val) < getDist(now_val)) {
        now_val = next_val;
        y = next_y;
      } else
        break;
    }
    while (1) {
      int next_y = y == v - 1 ? 0 : y + 1;
      int next_val = (X[x].first + Y[next_y].first) % q;
      if (getDist(next_val) < getDist(now_val)) {
        now_val = next_val;
        y = next_y;
      } else
        break;
    }
    best = min(best, Q(getDist(now_val), X[x].second, Y[y].second));
    {
      int ext_y = y == 0 ? v - 1 : y - 1;
      int ext_val = (X[x].first + Y[ext_y].first) % q;
      int ext_dist = getDist(ext_val);
      best = min(best, Q(ext_dist, X[x].second, Y[ext_y].second));
    }
    {
      int ext_y = y == v - 1 ? 0 : y + 1;
      int ext_val = (X[x].first + Y[ext_y].first) % q;
      int ext_dist = getDist(ext_val);
      best = min(best, Q(ext_dist, X[x].second, Y[ext_y].second));
    }
  }
  assert(v * v + v - 1 <= t);
  for (ll i = v * v + v; i <= t; i++) {
    int val = p * (a + i) % q;
    int dist = getDist(val);
    Q cand(dist, i / v, i % v);
    best = min(best, cand);
  }
  assert(get<0>(best) != q);
  return a + get<1>(best) * v + get<2>(best);
}
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int tim;
  cin >> tim;
  while (tim--) {
    int a, b, p, q;
    cin >> a >> b >> p >> q;
    int x = solve(a, b, p, q);
    assert(a <= x && x <= b);
    cout << solve(a, b, p, q) << "\n";
  }
  return 0;
}

```