Min-cost GCD

Computing the greatest common divisor of two natural numbers comes up often. In this problem you compute it at a smaller cost.

Seokhwan and Sangsu are natural number processors. A customer hands them one ordered pair of natural numbers, and they process the pair and hand it back.

• Seokhwan takes a pair $(x, y)$ and turns it into $(y, x \bmod y)$. One request costs $p$ won.
• Sangsu takes a pair $(x, y)$ and turns it into $(x - y, y)$ if $x \ge y$, or into $(x, y - x)$ if $x < y$. One request costs $q$ won.

For example:

• $(21, 5)$ becomes $(5, 1)$ with Seokhwan and $(16, 5)$ with Sangsu.
• $(5, 21)$ becomes $(21, 5)$ with Seokhwan and $(5, 16)$ with Sangsu.
• $(15, 21)$ becomes $(21, 15)$ with Seokhwan and $(15, 6)$ with Sangsu.

Seunghyun has an ordered pair of natural numbers $(a, b)$. He is good at mathematics, and he worked out that sending the pair to Seokhwan and Sangsu in a suitable order eventually reaches a pair with $ab = 0$. At that point $a + b$ is the greatest common divisor of the two numbers he started with.

Seunghyun then wondered what the smallest cost of reaching $ab = 0$ is once $a$, $b$, $p$, and $q$ are fixed. He cannot change the numbers himself, so he can only request processing. Compute that smallest cost for him.

The first line contains the number of test cases $T$.

Each of the next $T$ lines contains one test case. Line $i$ $(1 \le i \le T)$ contains four natural numbers $a_i$, $b_i$, $p_i$, $q_i$ separated by spaces.

• $1 \le T \le 100000$
• $1 \le a_i, b_i, p_i, q_i \le 10^{15}$ for every $i$ $(1 \le i \le T)$
• Every number in the input is a natural number.

For each test case, print the smallest cost in won on its own line. Seunghyun starts from the pair $(a_i, b_i)$, pays $p_i$ won for one request to Seokhwan and $q_i$ won for one request to Sangsu, and has to reach $a_i b_i = 0$ using processing requests only.

When $(a, b, p, q)$ is $(7, 3, 1, 1)$, $(8, 3, 1, 1)$, or $(7, 3, 3, 2)$, using Seokhwan alone is optimal.

When it is $(55, 34, 10, 9)$, both of them are needed. In the path below, --q--> is a request to Sangsu and --p--> is a request to Seokhwan.

(55, 34) --q--> (21, 34) --q--> (21, 13) --q--> (8, 13) --q--> (8, 5)
(8, 5) --p--> (5, 3) --q--> (2, 3) --q--> (2, 1) --p--> (1, 0)

Six requests to Sangsu and two to Seokhwan cost $6 \times 9 + 2 \times 10 = 74$ won.