#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long lint;
lint a,b,p,q;
bool calc_valid(lint x, lint y){
double t = log10(x)+log10(y);
return t < 18;
}
lint f(lint x, lint y){
if(x == 0 || y == 0) return 0;
if(x >= y){
lint cost1 = 2 * p;
lint cost2 = 0;
if(!calc_valid(q,x/y)) cost2 = 5e18;
else cost2 = q * (x/y);
if(x%y){
if(!calc_valid(q,y/(x%y))) cost2 = 5e18;
else cost2 += q * (y/(x%y));
}
else cost1 = p;
if(cost1 <= cost2) return f(y,x%y) + p;
else return f(x%y,y) + q*(x/y);
}
else{
if(!calc_valid(q,y/x)) return 5e18;
else return f(x,y%x) + q * (y/x);
}
}
void solve(){
scanf("%lld %lld %lld %lld",&a,&b,&p,&q);
if(a < b) printf("%lld\n",min(p + f(b,a),f(a,b)));
else printf("%lld\n",f(a,b));
}
int main(){
int t;
scanf("%d",&t);
while (t--) {
solve();
}
}
