#include <bits/stdc++.h>
using namespace std;
void solve() {
  long long a, b, p, q;
  cin >> a >> b >> p >> q;
  long long len = 1;
  while (len * len <= b - a + 1) len++;
  auto cal = [&](int index) { return (p * index % q); };
  auto insert = [&](int index, vector<pair<int, int>> &v, bool judge = true) {
    if (judge)
      if (index < a || index > b) return;
    auto value = cal(index);
    v.push_back(make_pair(value, index));
  };
  auto clean = [&](vector<pair<int, int>> &v) {
    sort(v.begin(), v.end());
    vector<pair<int, int>> tmp;
    for (auto x : v)
      if (tmp.empty() || x.first != tmp.back().first) tmp.push_back(x);
    v = tmp;
  };
  vector<pair<int, int>> small, big;
  vector<pair<int, int>> anss;
  for (int i = 0; i < len; i++) insert(i, small, false);
  clean(small);
  for (int i = a; i <= b; i += len) insert(i, big), insert(i, anss);
  clean(big);
  set<int> vals;
  vals.insert(q / 2);
  vals.insert(q / 2 + q % 2);
  vals.insert(q + q / 2);
  vals.insert(q + q / 2 + q % 2);
  for (int i = 0; i < len; i++) insert(b - i, anss);
  for (auto x : vals) {
    auto it1 = --small.end();
    auto it2 = small.end();
    for (auto [value, index] : big) {
      while (it1->first + value > x && it1 != small.begin()) it1--, it2--;
      insert(it1->second + index, anss);
      if (it2 != small.end()) insert(it2->second + index, anss);
    }
  }
  pair<int, int> ans(1e9 + 1, 1e9 + 1);
  for (auto [value, index] : anss) {
    for (auto x : {q / 2, q / 2 + q % 2}) {
      auto nv = abs(value - x);
      if (nv < ans.first || (nv == ans.first && index < ans.second)) {
        ans = make_pair(nv, index);
      }
    }
  }
  cout << ans.second << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

### Prompt

Create a solution in cpp for 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;
void solve() {
  long long a, b, p, q;
  cin >> a >> b >> p >> q;
  long long len = 1;
  while (len * len <= b - a + 1) len++;
  auto cal = [&](int index) { return (p * index % q); };
  auto insert = [&](int index, vector<pair<int, int>> &v, bool judge = true) {
    if (judge)
      if (index < a || index > b) return;
    auto value = cal(index);
    v.push_back(make_pair(value, index));
  };
  auto clean = [&](vector<pair<int, int>> &v) {
    sort(v.begin(), v.end());
    vector<pair<int, int>> tmp;
    for (auto x : v)
      if (tmp.empty() || x.first != tmp.back().first) tmp.push_back(x);
    v = tmp;
  };
  vector<pair<int, int>> small, big;
  vector<pair<int, int>> anss;
  for (int i = 0; i < len; i++) insert(i, small, false);
  clean(small);
  for (int i = a; i <= b; i += len) insert(i, big), insert(i, anss);
  clean(big);
  set<int> vals;
  vals.insert(q / 2);
  vals.insert(q / 2 + q % 2);
  vals.insert(q + q / 2);
  vals.insert(q + q / 2 + q % 2);
  for (int i = 0; i < len; i++) insert(b - i, anss);
  for (auto x : vals) {
    auto it1 = --small.end();
    auto it2 = small.end();
    for (auto [value, index] : big) {
      while (it1->first + value > x && it1 != small.begin()) it1--, it2--;
      insert(it1->second + index, anss);
      if (it2 != small.end()) insert(it2->second + index, anss);
    }
  }
  pair<int, int> ans(1e9 + 1, 1e9 + 1);
  for (auto [value, index] : anss) {
    for (auto x : {q / 2, q / 2 + q % 2}) {
      auto nv = abs(value - x);
      if (nv < ans.first || (nv == ans.first && index < ans.second)) {
        ans = make_pair(nv, index);
      }
    }
  }
  cout << ans.second << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

```