#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  long long t;
  cin >> t;
  while (t--) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    long long t = sqrt(b - a + 1) + 5;
    deque<pair<long long, long long>> A;
    for (long long x = a; x <= a + t && x <= b; x++) {
      A.push_back({(p * x) % q, x});
    }
    sort(A.begin(), A.end());
    for (int i = 1; i < (int)A.size();) {
      if (A[i].first == A[i - 1].first)
        A.erase(A.begin() + i);
      else
        i++;
    }
    pair<long long, long long> mx = {-1, -1};
    for (long long x = b; x >= a && x >= b - t; x--) {
      long long a = (p * x) % q;
      a = min(a, q - a);
      mx = max(mx, {a, -x});
    }
    for (long long i = 0; a + (t - 1) + t * i <= b; i++) {
      long long target = (q / 2 - i * t * p) % q;
      if (target < 0) target += q;
      auto it = upper_bound(A.begin(), A.end(), make_pair(target, b + 5));
      if (it != A.end()) {
        long long x = it->second + i * t;
        long long a = (p * x) % q;
        a = min(a, q - a);
        mx = max(mx, {a, -x});
      }
      if (it != A.begin()) {
        it--;
        long long x = it->second + i * t;
        long long a = (p * x) % q;
        a = min(a, q - a);
        mx = max(mx, {a, -x});
      }
    }
    cout << -mx.second << "\n";
  }
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>
#pragma GCC optimize("O3")
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  long long t;
  cin >> t;
  while (t--) {
    long long a, b, p, q;
    cin >> a >> b >> p >> q;
    long long t = sqrt(b - a + 1) + 5;
    deque<pair<long long, long long>> A;
    for (long long x = a; x <= a + t && x <= b; x++) {
      A.push_back({(p * x) % q, x});
    }
    sort(A.begin(), A.end());
    for (int i = 1; i < (int)A.size();) {
      if (A[i].first == A[i - 1].first)
        A.erase(A.begin() + i);
      else
        i++;
    }
    pair<long long, long long> mx = {-1, -1};
    for (long long x = b; x >= a && x >= b - t; x--) {
      long long a = (p * x) % q;
      a = min(a, q - a);
      mx = max(mx, {a, -x});
    }
    for (long long i = 0; a + (t - 1) + t * i <= b; i++) {
      long long target = (q / 2 - i * t * p) % q;
      if (target < 0) target += q;
      auto it = upper_bound(A.begin(), A.end(), make_pair(target, b + 5));
      if (it != A.end()) {
        long long x = it->second + i * t;
        long long a = (p * x) % q;
        a = min(a, q - a);
        mx = max(mx, {a, -x});
      }
      if (it != A.begin()) {
        it--;
        long long x = it->second + i * t;
        long long a = (p * x) % q;
        a = min(a, q - a);
        mx = max(mx, {a, -x});
      }
    }
    cout << -mx.second << "\n";
  }
}

```