#include <bits/stdc++.h>
using namespace std;
const int B = 33333;
int T;
long long a, b, p, q;
long long mod;
map<long long, long long> mp;
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    mod = q * 2;
    b -= a;
    mp.clear();
    for (int i = B - 1; i >= 0; i--) {
      long long x = 2 * p * i % mod;
      mp[x] = i;
    }
    long long ax = 2 * p * a % mod;
    long long ans = q + 1, px;
    int i;
    for (i = 0; i * B + B - 1 <= b; i++) {
      long long bx = 2 * p * i * B % mod;
      long long tx = (ax + bx) % mod;
      long long dx = (q + mod - tx) % mod;
      auto it = mp.upper_bound(dx);
      if (it != mp.begin()) {
        it--;
        long long res = (tx + (*it).first) % mod;
        if (abs(res - q) < ans) ans = abs(res - q), px = i * B + (*it).second;
      }
      it = mp.lower_bound(dx);
      if (it != mp.end()) {
        long long res = (tx + (*it).first) % mod;
        if (abs(res - q) < ans)
          ans = abs(res - q), px = i * B + (*it).second;
        else if (abs(res - q) == ans)
          px = min(px, i * B + (*it).second);
      }
    }
    for (int j = i * B; j <= b; j++) {
      long long tx = (ax + 2 * p * j) % mod;
      if (abs(tx - q) < ans) ans = abs(tx - q), px = j;
    }
    printf("%lld\n", px + a);
  }
  return 0;
}

### Prompt

Your task is to create 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;
const int B = 33333;
int T;
long long a, b, p, q;
long long mod;
map<long long, long long> mp;
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
    mod = q * 2;
    b -= a;
    mp.clear();
    for (int i = B - 1; i >= 0; i--) {
      long long x = 2 * p * i % mod;
      mp[x] = i;
    }
    long long ax = 2 * p * a % mod;
    long long ans = q + 1, px;
    int i;
    for (i = 0; i * B + B - 1 <= b; i++) {
      long long bx = 2 * p * i * B % mod;
      long long tx = (ax + bx) % mod;
      long long dx = (q + mod - tx) % mod;
      auto it = mp.upper_bound(dx);
      if (it != mp.begin()) {
        it--;
        long long res = (tx + (*it).first) % mod;
        if (abs(res - q) < ans) ans = abs(res - q), px = i * B + (*it).second;
      }
      it = mp.lower_bound(dx);
      if (it != mp.end()) {
        long long res = (tx + (*it).first) % mod;
        if (abs(res - q) < ans)
          ans = abs(res - q), px = i * B + (*it).second;
        else if (abs(res - q) == ans)
          px = min(px, i * B + (*it).second);
      }
    }
    for (int j = i * B; j <= b; j++) {
      long long tx = (ax + 2 * p * j) % mod;
      if (abs(tx - q) < ans) ans = abs(tx - q), px = j;
    }
    printf("%lld\n", px + a);
  }
  return 0;
}

```