#include <stdio.h>
#include <map>
struct pair {
long long x;
long long y;
bool operator <(const pair&a) const {return ((x < a.x) || (x == a.x && y < a.y));}
};
std::map<pair, long long> cache;
void do_sh(pair &in, pair &out)
{
out.x = in.y;
out.y = in.x % in.y;
}
void do_ss(pair &in, pair &out)
{
if (in.x >= in.y) {
out.x = in.x - in.y;
out.y = in.y;
} else {
out.x = in.x;
out.y = in.y - in.x;
}
}
long long cost(pair &x, long long p, long long q)
{
if (x.x == 0 || x.y == 0)
return 0LL;
std::map<pair, long long>::iterator it = cache.find(x);
if (it != cache.end())
return it->second;
long long cost_sh, cost_ss;
pair t;
do_sh(x, t);
cost_sh = p + cost(t, p, q);
do_ss(x, t);
cost_ss = q + cost(t, p, q);
long long ret = (cost_sh < cost_ss)? cost_sh : cost_ss;
cache[x] = ret;
return ret;
}
int main()
{
int T;
pair i;
long long p, q;
for (scanf("%d", &T); T; T--) {
cache.clear();
scanf("%lld%lld%lld%lld", &i.x, &i.y, &p, &q);
printf("%llu\n", cost(i, p, q));
}
}
