#include <bits/stdc++.h>
using namespace std;
long long T, a, b, p, q, blc;
map<long long, long long> Mp;
map<long long, long long>::iterator it;
void solve() {
  Mp.clear();
  blc = sqrt(b - a) + 1;
  for (long long i = 0; i < blc; i++) {
    if (!Mp.count((i * p * 2) % (q * 2))) Mp[(i * p * 2) % (q * 2)] = i;
  }
  it = Mp.begin();
  Mp[it->first + q * 2] = it->second;
  it = Mp.end();
  it--;
  Mp[it->first - q * 2] = it->second;
  long long ans = -1, mi = 1e15;
  for (long long i = a; i <= b; i += blc) {
    long long cr = ((q - i * p * 2) % (q * 2) + q * 2) % (q * 2);
    it = Mp.lower_bound(cr);
    if ((abs(cr - it->first) < mi ||
         (abs(cr - it->first) == mi && it->second + i < ans)) &&
        (it->second + i <= b && it->second + i >= a)) {
      mi = abs(cr - it->first);
      ans = it->second + i;
    }
    it--;
    if ((abs(cr - it->first) < mi ||
         (abs(cr - it->first) == mi && it->second + i < ans)) &&
        (it->second + i <= b && it->second + i >= a)) {
      mi = abs(cr - it->first);
      ans = it->second + i;
    }
    if (i + blc > b) {
      it = Mp.end();
      while (1) {
        it--;
        if ((abs(cr - it->first) < mi ||
             (abs(cr - it->first) == mi && it->second + i < ans)) &&
            (it->second + i <= b && it->second + i >= a)) {
          mi = abs(cr - it->first);
          ans = it->second + i;
        }
        if (it == Mp.begin()) break;
      }
    }
  }
  cout << ans << endl;
}
int main() {
  cin >> T;
  while (T--) {
    cin >> a >> b >> p >> q;
    if (p > q) {
      p %= q;
    }
    solve();
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 T, a, b, p, q, blc;
map<long long, long long> Mp;
map<long long, long long>::iterator it;
void solve() {
  Mp.clear();
  blc = sqrt(b - a) + 1;
  for (long long i = 0; i < blc; i++) {
    if (!Mp.count((i * p * 2) % (q * 2))) Mp[(i * p * 2) % (q * 2)] = i;
  }
  it = Mp.begin();
  Mp[it->first + q * 2] = it->second;
  it = Mp.end();
  it--;
  Mp[it->first - q * 2] = it->second;
  long long ans = -1, mi = 1e15;
  for (long long i = a; i <= b; i += blc) {
    long long cr = ((q - i * p * 2) % (q * 2) + q * 2) % (q * 2);
    it = Mp.lower_bound(cr);
    if ((abs(cr - it->first) < mi ||
         (abs(cr - it->first) == mi && it->second + i < ans)) &&
        (it->second + i <= b && it->second + i >= a)) {
      mi = abs(cr - it->first);
      ans = it->second + i;
    }
    it--;
    if ((abs(cr - it->first) < mi ||
         (abs(cr - it->first) == mi && it->second + i < ans)) &&
        (it->second + i <= b && it->second + i >= a)) {
      mi = abs(cr - it->first);
      ans = it->second + i;
    }
    if (i + blc > b) {
      it = Mp.end();
      while (1) {
        it--;
        if ((abs(cr - it->first) < mi ||
             (abs(cr - it->first) == mi && it->second + i < ans)) &&
            (it->second + i <= b && it->second + i >= a)) {
          mi = abs(cr - it->first);
          ans = it->second + i;
        }
        if (it == Mp.begin()) break;
      }
    }
  }
  cout << ans << endl;
}
int main() {
  cin >> T;
  while (T--) {
    cin >> a >> b >> p >> q;
    if (p > q) {
      p %= q;
    }
    solve();
  }
  return 0;
}

```