#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;
long long c1 = 0, c2 = 0;
if (a > b) c2 = 1LL<<62;
if (a < b) c1 = p, swap(a, b);
while (b) {
long long c = a / b;
long long d = a % b;
long long d1 = c1+p;
long long d2 = 1LL<<62;
if (1.0*c*q < (1LL<<61))
d2 = min(d2, c1+c*q);
if (1.0*c*q < (1LL<<61))
d1 = min(d1, c2+c*q);
d1 = min(d1, d2+p);
a = b;
b = d;
c1 = d1;
c2 = d2;
}
cout << min(c1, c2) << endl;
}
}
