#include <cstdio>
typedef long long lint;
lint a,b,p,q;
bool calc_valid(lint x, lint y){
while (y) {
if(x > 1e17) return 0;
x <<= 1;
y >>= 1;
}
return 1;
}
lint f(lint x, lint y){
if(x == 0 || y == 0) return 0;
lint c1 = f(y,x%y) + p; // 결코 답안은 10^17을 넘지 않는다
lint c2;
if(x >= y){
if(!calc_valid(q,x/y)) return c1;
else c2 = f(x%y,y) + q*(x/y);
}
else{
if(!calc_valid(q,y/x)) return c1;
else c2 = f(x,y%x) + q*(y/x);
}
return c1 < c2 ? c1 : c2;
}
void solve(){
scanf("%lld %lld %lld %lld",&a,&b,&p,&q);
printf("%lld\n",f(a,b));
}
int main(){
int t;
scanf("%d",&t);
while (t--) {
solve();
}
}
