#include <bits/stdc++.h>
using namespace std;
long long cal(long long a, long long b, long long c, long long n) {
  if (n == 0) return 0;
  return (b / c) * n + (a / c) * n * (n - 1) / 2 +
         cal(c, (a * n + b) % c, a % c, (a % c * n + b % c) / c);
}
long long a, b, p, q;
long long cnt(long long l, long long r, long long vl, long long vr) {
  long long sum = cal(p, l * p + q - vl, q, r - l + 1) -
                  cal(p, l * p + q - vr - 1, q, r - l + 1);
  return sum;
}
long long solve() {
  cin >> a >> b >> p >> q;
  long long l = 0, r = q / 2;
  while (l != r) {
    long long mid = (l + r) / 2;
    long long bruh = cnt(a, b, q / 2 - mid, (q + 1) / 2 + mid);
    if (bruh > 0)
      r = mid;
    else
      l = mid + 1;
  }
  long long gd = l;
  l = a, r = b;
  while (l != r) {
    long long mid = (l + r) / 2;
    long long bruh = cnt(a, mid, q / 2 - gd, (q + 1) / 2 + gd);
    if (bruh > 0)
      r = mid;
    else
      l = mid + 1;
  }
  return l;
}
int main() {
  int t;
  cin >> t;
  while (t--) cout << solve() << '\n';
}

### 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;
long long cal(long long a, long long b, long long c, long long n) {
  if (n == 0) return 0;
  return (b / c) * n + (a / c) * n * (n - 1) / 2 +
         cal(c, (a * n + b) % c, a % c, (a % c * n + b % c) / c);
}
long long a, b, p, q;
long long cnt(long long l, long long r, long long vl, long long vr) {
  long long sum = cal(p, l * p + q - vl, q, r - l + 1) -
                  cal(p, l * p + q - vr - 1, q, r - l + 1);
  return sum;
}
long long solve() {
  cin >> a >> b >> p >> q;
  long long l = 0, r = q / 2;
  while (l != r) {
    long long mid = (l + r) / 2;
    long long bruh = cnt(a, b, q / 2 - mid, (q + 1) / 2 + mid);
    if (bruh > 0)
      r = mid;
    else
      l = mid + 1;
  }
  long long gd = l;
  l = a, r = b;
  while (l != r) {
    long long mid = (l + r) / 2;
    long long bruh = cnt(a, mid, q / 2 - gd, (q + 1) / 2 + gd);
    if (bruh > 0)
      r = mid;
    else
      l = mid + 1;
  }
  return l;
}
int main() {
  int t;
  cin >> t;
  while (t--) cout << solve() << '\n';
}

```