#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;
long long limit;
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, long long cur_cost)
{
if (x.x == 0 || x.y == 0)
return cur_cost;
std::map<pair, long long>::iterator it = cache.find(x);
long long ret;
long long cost_sh = 0, cost_ss = 0;
pair t;
if (it != cache.end()) {
ret = it->second + cur_cost;
goto RET;
}
if (cur_cost + p <= limit) {
do_sh(x, t);
cost_sh = cost(t, p, q, cur_cost + p);
}
if (cur_cost + q <= limit) {
do_ss(x, t);
cost_ss = cost(t, p, q, cur_cost + q);
}
if (cost_sh && cost_ss) {
ret = (cost_sh < cost_ss)? cost_sh : cost_ss;
cache[x] = ret - cur_cost;
} else if (cost_sh) {
ret = cost_sh;
} else if (cost_ss) {
ret = cost_ss;
} else {
return 0;
}
RET:
if (ret <= limit) {
limit = ret;
return ret;
} else {
return 0;
}
}
long long check_limit(pair &x, long long p)
{
limit = 0;
pair i1, i2;
for (i1 = x; i1.x && i1.y; limit += p) {
do_sh(i1, i2);
i1 = i2;
}
}
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);
check_limit(i, p);
printf("%llu\n", cost(i, p, q, 0));
}
}
