#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stack>
#include <memory.h>
#include <assert.h>
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <queue>
#include <functional>
using namespace std;
// for subtask3
int p,q;
int Table[2005][2005];
int solve (int a, int b) {
if(a * b == 0) return 0;
if(Table[a][b] >= 0) return Table[a][b];
return Table[a][b] = min (
solve(b, a%b) + p,
(a > b ? solve(a-b, b) : solve(a, b-a)) + q
);
}
int main() {
int t; scanf("%d", &t);
memset(Table, -1, sizeof Table);
while(t--) {
int a,b;
scanf("%d%d%d%d", &a, &b, &p, &q);
printf("%d\n", solve(a,b));
}
return 0;
}
