#include <bits/stdc++.h>
using namespace std;
long long q, t;
int main() {
  ios::sync_with_stdio(false);
  cin >> t;
  for (int i = 1; i <= t; i++) {
    long long a, b, p, mn = 2e9 + 3, sav;
    cin >> a >> b >> p >> q;
    long long sq = 30000;
    vector<pair<long long, long long> > H, H2;
    long long crt = a * p * 2 % (2 * q);
    for (int j = a; j < a + sq; j++) {
      H.push_back({crt, j});
      crt = (crt + 2 * p) % (2 * q);
    }
    sort(H.begin(), H.end());
    for (auto it : H) {
      if (!H2.empty() && it.first == H2.back().first) continue;
      H2.push_back(it);
    }
    H = H2;
    long long q2 = q, j, I = 0;
    for (j = a + sq - 1; j <= b; j += sq, I++) {
      q2 = (q - 2LL * I * sq % (2 * q) * p) % (2 * q);
      if (q2 < 0) q2 += 2 * q;
      long long st = 0, dr = H.size() - 1;
      while ((dr - st) > 6) {
        long long mid1 = (st + st + dr) / 3;
        long long mid2 = (st + dr + dr) / 3;
        if (abs(H[mid2].first - q2) > abs(H[mid1].first - q2) ||
            (abs(H[mid2].first - q2) == abs(H[mid1].first - q2) &&
             H[mid1].second < H[mid2].second) ||
            mid1 == mid2) {
          dr = mid2 - 1;
        } else
          st = mid1 + 1;
      }
      for (; st <= dr; st++) {
        if (abs(H[st].first - q2) < mn ||
            (abs(H[st].first - q2) == mn && H[st].second + I * sq < sav)) {
          mn = abs(H[st].first - q2);
          sav = H[st].second + I * sq;
        }
      }
    }
    if (j >= b) j = max(a, j - sq);
    for (; j <= b; j++) {
      crt = 1LL * j * p * 2 % (2 * q);
      if (abs(q - crt) < mn) {
        mn = abs(q - crt);
        sav = j;
      }
    }
    cout << sav << '\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;
long long q, t;
int main() {
  ios::sync_with_stdio(false);
  cin >> t;
  for (int i = 1; i <= t; i++) {
    long long a, b, p, mn = 2e9 + 3, sav;
    cin >> a >> b >> p >> q;
    long long sq = 30000;
    vector<pair<long long, long long> > H, H2;
    long long crt = a * p * 2 % (2 * q);
    for (int j = a; j < a + sq; j++) {
      H.push_back({crt, j});
      crt = (crt + 2 * p) % (2 * q);
    }
    sort(H.begin(), H.end());
    for (auto it : H) {
      if (!H2.empty() && it.first == H2.back().first) continue;
      H2.push_back(it);
    }
    H = H2;
    long long q2 = q, j, I = 0;
    for (j = a + sq - 1; j <= b; j += sq, I++) {
      q2 = (q - 2LL * I * sq % (2 * q) * p) % (2 * q);
      if (q2 < 0) q2 += 2 * q;
      long long st = 0, dr = H.size() - 1;
      while ((dr - st) > 6) {
        long long mid1 = (st + st + dr) / 3;
        long long mid2 = (st + dr + dr) / 3;
        if (abs(H[mid2].first - q2) > abs(H[mid1].first - q2) ||
            (abs(H[mid2].first - q2) == abs(H[mid1].first - q2) &&
             H[mid1].second < H[mid2].second) ||
            mid1 == mid2) {
          dr = mid2 - 1;
        } else
          st = mid1 + 1;
      }
      for (; st <= dr; st++) {
        if (abs(H[st].first - q2) < mn ||
            (abs(H[st].first - q2) == mn && H[st].second + I * sq < sav)) {
          mn = abs(H[st].first - q2);
          sav = H[st].second + I * sq;
        }
      }
    }
    if (j >= b) j = max(a, j - sq);
    for (; j <= b; j++) {
      crt = 1LL * j * p * 2 % (2 * q);
      if (abs(q - crt) < mn) {
        mn = abs(q - crt);
        sav = j;
      }
    }
    cout << sav << '\n';
  }
  return 0;
}

```