#include <bits/stdc++.h>
using namespace std;
const int sq = 30000;
int main() {
  int t;
  cin >> t;
  while (t) {
    t--;
    int l, r, p, mod;
    pair<int, int> an = {2e9, -1};
    cin >> l >> r >> p >> mod;
    p %= mod;
    p *= 2, mod *= 2;
    map<int, int> ma;
    for (int a = 0; a < sq; a++) {
      int va = (1ll * a * p) % mod;
      if (ma.find(va) == ma.end()) ma[va] = a;
    }
    for (int a = l; a <= r; a += sq) {
      if (a + sq - 1 > r) {
        for (int b = a; b <= r; b++) {
          int di = abs(mod / 2 - ((1ll * b * p) % mod));
          an = min(an, {di, b});
        }
      } else {
        int l = mod / 2 - ((1ll * a * p) % mod);
        if (l < 0) l += mod;
        auto it = ma.upper_bound(l);
        if (it != ma.begin()) it--;
        int di = abs((1ll * a * p + (*it).first) % mod - mod / 2);
        an = min(an, {di, a + (*it).second});
        it++;
        if (it != ma.end()) {
          int di = abs((1ll * a * p + (*it).first) % mod - mod / 2);
          an = min(an, {di, a + (*it).second});
        }
      }
    }
    cout << an.second << "\n";
  }
}

### Prompt

Your task is to create 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;
const int sq = 30000;
int main() {
  int t;
  cin >> t;
  while (t) {
    t--;
    int l, r, p, mod;
    pair<int, int> an = {2e9, -1};
    cin >> l >> r >> p >> mod;
    p %= mod;
    p *= 2, mod *= 2;
    map<int, int> ma;
    for (int a = 0; a < sq; a++) {
      int va = (1ll * a * p) % mod;
      if (ma.find(va) == ma.end()) ma[va] = a;
    }
    for (int a = l; a <= r; a += sq) {
      if (a + sq - 1 > r) {
        for (int b = a; b <= r; b++) {
          int di = abs(mod / 2 - ((1ll * b * p) % mod));
          an = min(an, {di, b});
        }
      } else {
        int l = mod / 2 - ((1ll * a * p) % mod);
        if (l < 0) l += mod;
        auto it = ma.upper_bound(l);
        if (it != ma.begin()) it--;
        int di = abs((1ll * a * p + (*it).first) % mod - mod / 2);
        an = min(an, {di, a + (*it).second});
        it++;
        if (it != ma.end()) {
          int di = abs((1ll * a * p + (*it).first) % mod - mod / 2);
          an = min(an, {di, a + (*it).second});
        }
      }
    }
    cout << an.second << "\n";
  }
}

```