Min-cost GCD Batch Compilation commands

두 자연수의 최대공약수를 구하는 것은 매우 중요합니다. 이 문제에서는 좀더 적은 비용으로 최대공약수를 구하고자 합니다.

석환이와 상수는 자연수 가공업자입니다. 이들은 구매자가 두 자연수의 순서쌍 하나를 의뢰하면, 이를 적당히 가공하여 돌려주는 일을 합니다.

1. 석환이는 두 자연수의 순서쌍 $(x, y)$를 받아, $(y, x \mod y)$로 바꿉니다. 이 작업을 한 번 하는 데 $p$원이 듭니다.
2. 상수는 두 자연수의 순서쌍 $(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 ≤ i ≤ T)번째 줄에는 네 개의 자연수 ai, bi, pi, qi가 공백을 사이로 두고 주어집니다.

출력 형식

각 테스트 케이스에 대해, 승현이가 처음 두 자연수의 순서쌍 (ai, bi)를 가지고 있고, 석환이에게 한 번 의뢰하는데 pi원, 상수에게 한 번 의뢰하는 데 qi원이 들 때, 가공 의뢰만으로 aibi = 0을 만족시키기 위해 들여야 할 최소 비용을 원 단위로 출력합니다.

제약 조건

• $1 \le T \le 100, 000$
• 모든 자연수 $i$ ($1 \le i \le T$)에 대해, $1 \le a_{i}, b_{i}, p_{i}, q_{i} \le 10^{15}$
• 입력에서 주어지는 모든 수는 자연수입니다.

부분문제

부분문제	점수	T	max{a**i, b**i}	추가 제약 조건
1	14	≤ 100	≤ 100	모든 자연수 i (1 ≤ i ≤ T)에 대해, p**i, q**i ≤ 100
2	16	≤ 100,000	≤ 2,000	p1 = p2 = ... = p**T ≤ 2,000, q1 = q2 = ... = q**T ≤ 2,000
3	27	≤ 1,000	≤ 109	-
4	43	≤ 100,000	≤ 1015	-

예제

입력

4
7 3 1 1
8 3 1 1
7 3 3 2
55 34 10 9

출력

2
3
6
74

설명

첫 번째, 두 번째, 세 번째 입력 모두에서 석환이에게만 맡기는 것이 최선입니다.

네 번째 입력에서는 상수와 석환이 모두에게 맡겨야 합니다. 변화를 살펴보자면 아래와 같습니다. 오른쪽으로 향하는 화살표는 상수의 가공을, 아래로 향하는 화살표는 석환이의 가공을 의미합니다.