Min-cost GCD Batch 컴파일 명령

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

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

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

출력 형식

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

제약 조건

• 1 ≤ T ≤ 100, 000
• 모든 자연수 i (1 ≤ i ≤ T)에 대해, 1 ≤ a_i, b_i, p_i,  q_i ≤ 10¹⁵
• 입력에서 주어지는 모든 수는 자연수입니다.

부분문제

예제

설명

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

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