#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
long long comp(long long a, long long b, long long p, long long q) {
if (1.0*b*q > a*p*2) return a*p;
return min(a*p, b*q);
}
int main()
{
int T;
cin >> T;
for (int i=0; i<T; i++) {
long long a, b, p, q;
cin >> a >> b >> p >> q;
long long res = 0;
while (a && b && (a % b)) {
long long c = a % b;
long long d = b % c;
res += comp(2, a/b + b/c, p, q);
a = c;
b = d;
}
if (b)
res += comp(1, a/b, p, q);
cout << res << endl;
}
}
