#include <stdio.h>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>

typedef long long int lld;
const lld infL = 1LL << 60;

// Find x that abs(sin(p/q pi x)) is the largest in [start, end).
int solve(lld start, lld end, lld p, lld q){
	
	// Construct base intervals
	lld interval = 1;
	while(interval * interval < end - start) interval++;
	
	// Period is q/p. x should be the closest to the middle of period(q/2p).
	// x % (2q/2p) should be the closest to q/2p => 2px % 2q should be the closest to q.
	// Construct remainders
	std::vector<std::pair<lld, lld>> remainders, remainders_copy;
	for(lld i=start; i<start+interval; i++){
		lld key = 2*p*i % (2*q);
		remainders.push_back({key, i});
	}
	std::sort(remainders.begin(), remainders.end());
	remainders_copy = remainders; remainders.clear();
	remainders.push_back(remainders_copy[0]);
	for(int i=1; i<remainders_copy.size(); i++){
		if(remainders_copy[i].first != remainders_copy[i-1].first)
			remainders.push_back(remainders_copy[i]);
	} remainders_copy.clear();
	
	
	// Look in [start + i*interval, start + (i+1)*interval), start + (i+1)*interval <= end.
	// x + i*interval ~= q/2p => x ~= q/2p - i*interval.
	//printf("base interval = %lld\n", interval);
	lld answervalue = -1, answerdistance = infL, iteration = 0;
	for(iteration = 0; start + (iteration+1)*interval <= end; iteration++){
		lld look = q - iteration * interval * 2 * p; // iteration * interval <= interval^2 <= end - start <= 10^8
		look %= (2*q); if(look < 0) look += 2*q;
		//printf("Looking %lld in [%lld, %lld)\n", look, start + iteration*interval, start + (iteration+1)*interval);
		lld baseindex = std::lower_bound(remainders.begin(), remainders.end(), std::make_pair(look, -infL)) - remainders.begin();
		for(int j=0; j>=-1; j--){
			lld thisindex = (baseindex+j) % remainders.size(); if(thisindex < 0) thisindex += remainders.size();
			lld thisvalue = remainders[thisindex].second + iteration * interval;
			lld thisdistance = look - remainders[thisindex].first; 
			if(thisdistance < 0) thisdistance *= -1;
			if(thisdistance > q) thisdistance = 2*q - thisdistance;
			//printf("  Looking baseindex = %lld, thisindex = %lld, thisfirst = %lld, thisvalue = %lld (distance %lld)\n", 
			//	baseindex, thisindex, thisvalue, remainders[thisindex].first, thisdistance);
			if(std::make_pair(thisdistance, thisvalue) < std::make_pair(answerdistance, answervalue)){
				answervalue = thisvalue;
				answerdistance = thisdistance;
				//printf("  Answer changed to %lld (distance %lld)\n", answervalue, answerdistance);
			}
		}
	} 
	
	// Brute force for remaining ranges
	for(lld v = start + iteration * interval; v < end; v++){
		//printf("Looking %lld\n", v);
		lld thisdistance = (2*p*v) % (2*q) - q; if(thisdistance < 0) thisdistance *= -1;
		if(std::make_pair(thisdistance, v) < std::make_pair(answerdistance, answervalue)){
			answerdistance = thisdistance;
			answervalue = v;
			//printf("  Answer changed to %lld (distance %lld)\n", answervalue, answerdistance);
		}
	}
	
	return answervalue;
}

int main(void){
	int testcases; scanf("%d", &testcases);
	for(int t=0; t<testcases; t++){
		lld a, b, p, q; scanf("%lld %lld %lld %lld", &a, &b, &p, &q);
		//printf("Case #%d: ", t+1);
		printf("%d\n", solve(a, b+1, p, q));
	}
	return 0;
}