#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    long long s, d, p, q;
    cin >> s >> d >> p >> q;
    d = d + 1 - s;
    long long B = 30000;
    map<long long, int> m;
    long long mod = 2 * q;
    auto add = [&](int i) {
      long long v = ((i * B + s) % mod * 2 * p % mod + mod) % mod;
      if (!m.count(v)) m[v] = i;
    };
    pair<long long, long long> ans(1e18, -1);
    for (int i = 0; i * B + B - 1 < d; i++) add(i);
    for (int i = min(B, d) - 1; i >= 0; i--) {
      if (d / B * B + i == d - 1) add(d / B);
      long long v = 2 * p * i % mod;
      for (long long t : {q, q * 3}) {
        auto it = m.upper_bound(t - v);
        if (it != m.end())
          ans = min(ans, {abs(it->first + v - t), it->second * B + i + s});
        if (it != m.begin())
          ans = min(ans, {abs(prev(it)->first + v - t),
                          prev(it)->second * B + i + s});
      }
    }
    cout << ans.second << endl;
  }
}

### Prompt

In cpp, your task is to solve 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 main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    long long s, d, p, q;
    cin >> s >> d >> p >> q;
    d = d + 1 - s;
    long long B = 30000;
    map<long long, int> m;
    long long mod = 2 * q;
    auto add = [&](int i) {
      long long v = ((i * B + s) % mod * 2 * p % mod + mod) % mod;
      if (!m.count(v)) m[v] = i;
    };
    pair<long long, long long> ans(1e18, -1);
    for (int i = 0; i * B + B - 1 < d; i++) add(i);
    for (int i = min(B, d) - 1; i >= 0; i--) {
      if (d / B * B + i == d - 1) add(d / B);
      long long v = 2 * p * i % mod;
      for (long long t : {q, q * 3}) {
        auto it = m.upper_bound(t - v);
        if (it != m.end())
          ans = min(ans, {abs(it->first + v - t), it->second * B + i + s});
        if (it != m.begin())
          ans = min(ans, {abs(prev(it)->first + v - t),
                          prev(it)->second * B + i + s});
      }
    }
    cout << ans.second << endl;
  }
}

```