func_code_string: #include <bits/stdc++.h>   using namespace std;   const int tmw168 = 1e5;   long long a, b, p, q, invp;   long long gcd(long long x, long long y) {     if (y == 0) return x;     return gcd(y, x % y);   }   long long test(long long r) {     r = r * invp % q;     r += a / q * q;     if (r < a) r += q;     return r;   }   int f(long long x, long long y) {     if (min(x, y) > b) return false;     cout << min(x, y) <<   n ;     return true;   }   long long inv(long long a, long long b) {     long long s = 0, t = 1;     long long old_s = 1, old_t = 0;     long long r = b, old_r = a;     while (r != 0) {       long long quotient = old_r / r;       long long tr = r;       r = old_r - quotient * r;       old_r = tr;       long long ts = s;       s = old_s - quotient * s;       old_s = ts;       long long tt = t;       t = old_t - quotient * t;       old_t = tt;     }     old_s = (old_s % q + q) % q;     return old_s;   }   void solve() {     cin >> a >> b >> p >> q;     long long g = gcd(p, q);     p /= g;     q /= g;     p %= q;     int ma = -1, gd = 0;     if (b - a < tmw168) {       for (int i = a; i <= b; i++) {         int cur = min(i * p % q, q - i * p % q);         if (cur > ma) {           ma = cur;           gd = i;         }       }       cout << gd <<   n ;       return;     }     invp = inv(p, q);     for (int i = 0; i < q; i++) {       if (f(test(q / 2 - i), test((q + 1) / 2 + i))) return;     }   }   int main() {     ios::sync_with_stdio(false);     int t;     cin >> t;     while (t--) solve();   }   