#include <bits/stdc++.h>
using namespace std;
int t;
long long a, b, p, q;
void update(long long a, long long b, long long &diff, long long &ans,
            int cur) {
  if (a > b) swap(a, b);
  int tmp = min(b - a, a + (2 * q) - b);
  if (tmp < diff || (tmp == diff && cur < ans)) {
    ans = cur;
    diff = tmp;
  }
}
vector<pair<long long, long long> > v;
int main() {
  cin >> t;
  while (t--) {
    v.clear();
    cin >> a >> b >> p >> q;
    long long target = q, diff = q, ans = a;
    int t = sqrt(b - a + 1);
    for (int i = a, j = 0; j < t; i++, j++)
      v.push_back(make_pair((2 * p * i) % (2 * q), i));
    sort(v.begin(), v.end());
    for (int i = 0, j = 0; i < t; i++, j += t) {
      if (target > v.back().first) {
        long long t = v.back().first;
        int p = lower_bound(v.begin(), v.end(), make_pair(t, -1ll)) - v.begin();
        update(v[p].first, target, diff, ans, j + v[p].second);
        update(v[0].first, target, diff, ans, j + v[0].second);
      } else {
        int p = upper_bound(v.begin(), v.end(), make_pair(target, -1ll)) -
                v.begin();
        update(v[p].first, target, diff, ans, j + v[p].second);
        int q;
        if (p == 0)
          q = v.size() - 1;
        else
          q = p - 1;
        long long t = v[q].first;
        int r = lower_bound(v.begin(), v.end(), make_pair(t, -1ll)) - v.begin();
        update(v[r].first, target, diff, ans, j + v[r].second);
      }
      target = ((target - 2 * p * t % (2 * q)) % (2 * q) + 2 * q) % (2 * q);
    }
    for (int i = a + t * t; i <= b; i++) {
      long long cur = (2 * p * i) % (2 * q);
      update(cur, q, diff, ans, i);
    }
    cout << ans << endl;
  }
  return 0;
}

### Prompt

Generate 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;
int t;
long long a, b, p, q;
void update(long long a, long long b, long long &diff, long long &ans,
            int cur) {
  if (a > b) swap(a, b);
  int tmp = min(b - a, a + (2 * q) - b);
  if (tmp < diff || (tmp == diff && cur < ans)) {
    ans = cur;
    diff = tmp;
  }
}
vector<pair<long long, long long> > v;
int main() {
  cin >> t;
  while (t--) {
    v.clear();
    cin >> a >> b >> p >> q;
    long long target = q, diff = q, ans = a;
    int t = sqrt(b - a + 1);
    for (int i = a, j = 0; j < t; i++, j++)
      v.push_back(make_pair((2 * p * i) % (2 * q), i));
    sort(v.begin(), v.end());
    for (int i = 0, j = 0; i < t; i++, j += t) {
      if (target > v.back().first) {
        long long t = v.back().first;
        int p = lower_bound(v.begin(), v.end(), make_pair(t, -1ll)) - v.begin();
        update(v[p].first, target, diff, ans, j + v[p].second);
        update(v[0].first, target, diff, ans, j + v[0].second);
      } else {
        int p = upper_bound(v.begin(), v.end(), make_pair(target, -1ll)) -
                v.begin();
        update(v[p].first, target, diff, ans, j + v[p].second);
        int q;
        if (p == 0)
          q = v.size() - 1;
        else
          q = p - 1;
        long long t = v[q].first;
        int r = lower_bound(v.begin(), v.end(), make_pair(t, -1ll)) - v.begin();
        update(v[r].first, target, diff, ans, j + v[r].second);
      }
      target = ((target - 2 * p * t % (2 * q)) % (2 * q) + 2 * q) % (2 * q);
    }
    for (int i = a + t * t; i <= b; i++) {
      long long cur = (2 * p * i) % (2 * q);
      update(cur, q, diff, ans, i);
    }
    cout << ans << endl;
  }
  return 0;
}

```