//
// main.cpp
// 2. Min-cost GCD (mcg)
//
// Created by KJBS2 on 2014. 12. 24..
// Copyright (c) 2014년 KJBS2. All rights reserved.
//
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
#define MAX_LL ((ll)1*0x7fffffff*0x7fffffff)
ll A, B, P, Q;
ll X, Y, Z, W;
void PROCESS() {
scanf("%lld%lld%lld%lld", &A, &B, &P, &Q);
X = 0; Y = MAX_LL;
for(; A!=0 && B!=0;) {
ll C = A % B, D = A / B;
Z = X + P;
if( (MAX_LL - X) / Q >= D) W = X + D * Q;
else W = MAX_LL;
if(Y != MAX_LL) {
ll temp;
temp = Y + P + P;
Z = min(Z, temp);
if( (MAX_LL - Y) / Q >= D) temp = Y + D * Q;
else temp = MAX_LL;
Z = min(Z, temp);
if( (MAX_LL - Y - P) / Q >= D) temp = Y + P + D * Q;
else temp = MAX_LL;
W = min(W, temp);
}
X = Z;
Y = W;
A = B; B = C;
}
printf("%lld\n", min(X, Y) );
}
int main() {
int T; scanf("%d", &T);
for(int i=0; i<T; i++)
PROCESS();
return 0;
}
