#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 5, INF = 1e9 + 5;
int a, b, p, q, p2, q2, bs, tot;
pair<long long, int> c[N], ans;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d%d", &a, &b, &p, &q);
    p2 = 2 * p;
    q2 = 2 * q;
    bs = sqrt(b - a + 1);
    tot = 0;
    for (int i = 0; i < bs; i++)
      c[++tot] = make_pair((long long)p2 * (a + i) % q2, i);
    sort(c + 1, c + tot + 1);
    tot = 0;
    for (int i = 1; i <= bs; i++)
      if (i == 1 || c[i].first != c[i - 1].first) c[++tot] = c[i];
    c[0] = c[tot];
    c[tot + 1] = c[1];
    int tp = (long long)p2 * bs % q2, pls = 0, pl2 = a;
    ans = make_pair(INF, INF);
    for (int i = 0, d; i < bs;
         i++, pls = ((long long)pls + tp) % q2, pl2 += bs) {
      d = lower_bound(c + 1, c + tot + 1,
                      make_pair(((long long)q + q2 - pls) % q2, 0)) -
          c - 1;
      ans = min(ans,
                make_pair(abs((c[d].first + pls) % q2 - q), c[d].second + pl2));
      ans = min(ans, make_pair(abs((c[d + 1].first + pls) % q2 - q),
                               c[d + 1].second + pl2));
    }
    for (int i = a + bs * bs; i <= b; i++)
      ans = min(ans, make_pair(abs((long long)p2 * i % q2 - q), i));
    printf("%d\n", ans.second);
  }
  return 0;
}

### Prompt

Please create a solution in Cpp 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 N = 4e4 + 5, INF = 1e9 + 5;
int a, b, p, q, p2, q2, bs, tot;
pair<long long, int> c[N], ans;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d%d", &a, &b, &p, &q);
    p2 = 2 * p;
    q2 = 2 * q;
    bs = sqrt(b - a + 1);
    tot = 0;
    for (int i = 0; i < bs; i++)
      c[++tot] = make_pair((long long)p2 * (a + i) % q2, i);
    sort(c + 1, c + tot + 1);
    tot = 0;
    for (int i = 1; i <= bs; i++)
      if (i == 1 || c[i].first != c[i - 1].first) c[++tot] = c[i];
    c[0] = c[tot];
    c[tot + 1] = c[1];
    int tp = (long long)p2 * bs % q2, pls = 0, pl2 = a;
    ans = make_pair(INF, INF);
    for (int i = 0, d; i < bs;
         i++, pls = ((long long)pls + tp) % q2, pl2 += bs) {
      d = lower_bound(c + 1, c + tot + 1,
                      make_pair(((long long)q + q2 - pls) % q2, 0)) -
          c - 1;
      ans = min(ans,
                make_pair(abs((c[d].first + pls) % q2 - q), c[d].second + pl2));
      ans = min(ans, make_pair(abs((c[d + 1].first + pls) % q2 - q),
                               c[d + 1].second + pl2));
    }
    for (int i = a + bs * bs; i <= b; i++)
      ans = min(ans, make_pair(abs((long long)p2 * i % q2 - q), i));
    printf("%d\n", ans.second);
  }
  return 0;
}

```