#include <bits/stdc++.h>
using namespace std;
constexpr int MAGIC = 30000;
int t, cnt;
pair<long long, long long> pp[MAGIC], ans;
long long a, b, p, q;
long long g(long long x) { return 2 * p * x % (2 * q); }
int main() {
  scanf("%d", &t);
  while (t--) {
    cnt = 1;
    ans.first = LLONG_MAX;
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    for (int i = 0; i < MAGIC; i++) pp[i] = {g(a + i), i};
    sort(pp, pp + MAGIC);
    for (int i = 1; i < MAGIC; i++)
      if (pp[i].first != pp[cnt - 1].first) pp[cnt++] = pp[i];
    b++;
    for (long long at = a; at < b; at += MAGIC)
      if (b - at >= MAGIC) {
        long long tar = (q + 2 * q - g(at - a)) % (2 * q);
        int ind = lower_bound(pp, pp + cnt, make_pair(tar, LLONG_MIN)) - pp;
        if (ind == cnt)
          ans = min(ans, {pp[0].first + 2 * q - tar, at + pp[0].second});
        else
          ans = min(ans, {pp[ind].first - tar, at + pp[ind].second});
        if (ind == 0)
          ans = min(ans,
                    {tar + 2 * q - pp[cnt - 1].first, at + pp[cnt - 1].second});
        else
          ans = min(ans, {tar - pp[ind - 1].first, at + pp[ind - 1].second});
      } else {
        for (long long i = at; i < b; i++) ans = min(ans, {abs(g(i) - q), i});
        break;
      }
    printf("%lld\n", ans.second);
  }
}

### Prompt

Your challenge is to write 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;
constexpr int MAGIC = 30000;
int t, cnt;
pair<long long, long long> pp[MAGIC], ans;
long long a, b, p, q;
long long g(long long x) { return 2 * p * x % (2 * q); }
int main() {
  scanf("%d", &t);
  while (t--) {
    cnt = 1;
    ans.first = LLONG_MAX;
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    for (int i = 0; i < MAGIC; i++) pp[i] = {g(a + i), i};
    sort(pp, pp + MAGIC);
    for (int i = 1; i < MAGIC; i++)
      if (pp[i].first != pp[cnt - 1].first) pp[cnt++] = pp[i];
    b++;
    for (long long at = a; at < b; at += MAGIC)
      if (b - at >= MAGIC) {
        long long tar = (q + 2 * q - g(at - a)) % (2 * q);
        int ind = lower_bound(pp, pp + cnt, make_pair(tar, LLONG_MIN)) - pp;
        if (ind == cnt)
          ans = min(ans, {pp[0].first + 2 * q - tar, at + pp[0].second});
        else
          ans = min(ans, {pp[ind].first - tar, at + pp[ind].second});
        if (ind == 0)
          ans = min(ans,
                    {tar + 2 * q - pp[cnt - 1].first, at + pp[cnt - 1].second});
        else
          ans = min(ans, {tar - pp[ind - 1].first, at + pp[ind - 1].second});
      } else {
        for (long long i = at; i < b; i++) ans = min(ans, {abs(g(i) - q), i});
        break;
      }
    printf("%lld\n", ans.second);
  }
}

```