#include <stdio.h>
#include <algorithm>
#include <math.h>
#define INF 0x7fffffffffffffff
using namespace std;
int T, Cnt;
long long A, B, P, Q, D[1001][2];
double LX, LY, LQ, LI=log(INF);
void gcd(long long X, long long Y) {
if(!Y) {
printf("%lld\n",min(D[Cnt][0],D[Cnt][1]));
return;
}
LX=log(X);
LY=log(Y);
Cnt++;
if(LX-LY+LQ>LI || D[Cnt-1][1]+X/Y*Q<0)
D[Cnt][0]=D[Cnt-1][0]+P;
else
D[Cnt][0]=min(D[Cnt-1][0]+P,D[Cnt-1][1]+X/Y*Q);
if(LX-LY+LQ>LI || D[Cnt-1][0]+X/Y*Q<0)
D[Cnt][1]=INF;
else
D[Cnt][1]=D[Cnt-1][0]+X/Y*Q;
gcd(Y,X%Y);
}
int main(void) {
int i;
scanf("%d",&T);
for(i=1 ; i<=T ; i++) {
scanf("%lld %lld %lld %lld",&A,&B,&P,&Q);
LQ=log(Q);
Cnt=1;
if(A>B) {
D[Cnt][0]=0;
D[Cnt][1]=INF;
}
else if(A<B) {
D[Cnt][0]=P;
D[Cnt][1]=0;
}
else
D[Cnt][0]=D[Cnt][1]=0;
if(A>B)
gcd(A,B);
else
gcd(B,A);
}
return 0;
}
