최소 비용 최대공약수

두 자연수의 최대공약수를 구하는 일은 중요하다. 이 문제에서는 최대공약수를 더 적은 비용으로 구하려고 한다.

석환이와 상수는 자연수 가공업자다. 구매자가 자연수 순서쌍 하나를 맡기면 그 순서쌍을 적당히 가공해서 돌려준다.

• 석환이는 순서쌍 $(x, y)$를 받아 $(y, x \bmod y)$로 바꾼다. 한 번 맡기는 데 $p$원이 든다.
• 상수는 순서쌍 $(x, y)$를 받아 $x \ge y$이면 $(x - y, y)$로, $x < y$이면 $(x, y - x)$로 바꾼다. 한 번 맡기는 데 $q$원이 든다.

예를 들면 이렇다.

• $(21, 5)$를 석환이에게 맡기면 $(5, 1)$이 되고, 상수에게 맡기면 $(16, 5)$가 된다.
• $(5, 21)$을 석환이에게 맡기면 $(21, 5)$가 되고, 상수에게 맡기면 $(5, 16)$이 된다.
• $(15, 21)$을 석환이에게 맡기면 $(21, 15)$가 되고, 상수에게 맡기면 $(15, 6)$이 된다.

승현이는 자연수 순서쌍 $(a, b)$를 가지고 있다. 수학에 밝은 승현이는 석환이와 상수에게 순서를 잘 정해 맡기면 결국 $ab = 0$인 순서쌍에 도달한다는 것을 알아냈다. 그때 $a + b$는 처음 두 자연수의 최대공약수다.

이렇게 최대공약수를 구하던 승현이는, $a$와 $b$와 $p$와 $q$가 정해져 있을 때 $ab = 0$을 만드는 데 드는 최소 비용이 궁금해졌다. 승현이는 수를 직접 바꿀 수 없고 가공만 의뢰할 수 있다. 승현이를 대신해 그 최소 비용을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

다음 $T$개 줄에 테스트 케이스가 하나씩 주어진다. 그중 $i$ $(1 \le i \le T)$번째 줄에는 네 자연수 $a_i$, $b_i$, $p_i$, $q_i$가 공백을 사이에 두고 주어진다.

• $1 \le T \le 100000$
• 모든 $i$ $(1 \le i \le T)$에 대해 $1 \le a_i, b_i, p_i, q_i \le 10^{15}$
• 입력으로 주어지는 수는 모두 자연수다.

각 테스트 케이스마다 한 줄에 하나씩, 최소 비용을 원 단위로 출력한다. 승현이는 순서쌍 $(a_i, b_i)$에서 시작하고, 석환이에게 한 번 맡기는 데 $p_i$원, 상수에게 한 번 맡기는 데 $q_i$원을 쓰며, 가공 의뢰만으로 $a_i b_i = 0$을 만들어야 한다.

$(a, b, p, q)$가 $(7, 3, 1, 1)$, $(8, 3, 1, 1)$, $(7, 3, 3, 2)$일 때는 석환이에게만 맡기는 것이 최선이다.

$(55, 34, 10, 9)$일 때는 두 사람 모두에게 맡겨야 한다. 아래 경로에서 --q-->는 상수의 가공, --p-->는 석환이의 가공이다.

(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)

상수의 가공을 여섯 번, 석환이의 가공을 두 번 써서 비용은 $6 \times 9 + 2 \times 10 = 74$원이다.