#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;
struct state {
long long a, b, cost;
state(long long _a, long long _b, long long _cost) {
cost = _cost;
a = _a;
b = _b;
};
bool operator < (const state & another) const {
if (cost != another.cost) return cost < another.cost;
if (a != another.a) return a < another.a;
return b < another.b;
}
};
int main()
{
int T;
cin >> T;
for (int i=0; i<T; i++) {
long long a, b, p, q;
cin >> a >> b >> p >> q;
set<state> S;
S.insert(state(a, b, 0));
long long res = 1LL<<62;
set<pair<long long, long long> > seen;
while (1) {
set<state>::iterator it = S.begin();
state now = *it;
S.erase(it);
if (seen.find(pair<long long, long long>(now.a, now.b)) != seen.end()) continue;
seen.insert(pair<long long, long long>(now.a, now.b));
if (now.a == 0 || now.b == 0) {
res = now.cost;
break;
}
S.insert(state(now.b, now.a%now.b, now.cost+p));
if (now.a >= now.b) {
long long c = now.a / now.b;
if (1.0*c*q < (1LL<<62))
S.insert(state(now.a%now.b, now.b, now.cost+c*q));
} else {
long long c = now.b / now.a;
if (1.0*c*q < (1LL<<62)) {
S.insert(state(now.a, now.b%now.a, now.cost+c*q));
}
}
}
cout << res << endl;
}
}
