#include <unordered_map>
#include <cstdio>
#include <algorithm>
using namespace std;
class llhash
{
public:
size_t operator()(const pair<long long, long long>& x) const
{
size_t h = (x.first << 32) | ((x.second << 32) >> 32);
return h;
}
};
unordered_map<pair<long long, long long>, long long, llhash> dp;
long long a, b, p, q;
const long long INF = 1000000ll * 1000000ll * 500000ll;
long long getAns(long long a, long long b)
{
if(a == 0 || b == 0) return 0;
pair<long long, long long> cur = make_pair(a, b);
if(dp.count(cur)) return dp[cur];
long long ret = p + getAns(b, a % b);
if(a >= b)
{
long long howMany = a / b;
if(howMany <= ret / (double)q)
{
long long cand = howMany * q + getAns(a % b, b);
ret = min(cand, ret);
}
}
else
{
long long howMany = b / a;
if(howMany <= ret / (double)q)
{
long long cand = howMany * q + getAns(a, b % a);
ret = min(cand, ret);
}
}
return dp[cur] = ret;
}
int main(void)
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%lld %lld %lld %lld", &a, &b, &p, &q);
dp.clear();
printf("%lld\n", getAns(a, b));
}
return 0;
}
