27521번 - 공약수 (More Huge)

어느 날 2436번: 공약수를 해결한 흐즈로는 문제가 너무 시시하다고 생각했습니다. 그래서 흐즈로는 입력될 수 있는 값의 제한을 훨씬 늘려버려서, 최대 $10^{18}$까지의 양의 정수가 입력될 수 있는 경우를 생각해 보았습니다. 그럼에도 여전히 문제가 풀 만하다고 생각하여, 흐즈로는 이 문제에 대한 쿼리를 최대 $50000$개까지 물어보기로 하였습니다. 여러분이 해결해야 하는 문제는 다음과 같습니다.

쿼리가 총 $Q$ ($1 \le Q \le 50\,000$)개 주어집니다. 여러분이 답해야 하는 쿼리는 다음과 같습니다.

• $G \, L$: 최대공약수가 $G$이고 최소공배수가 $L$인 두 정수의 순서쌍 $(a,b)$ 중에서 $a+b$가 가장 작은 것을 출력합니다. 조건을 만족하는 순서쌍이 2개 이상 존재한다면 그 중 $a$가 가장 작은 것을 출력합니다. 모든 쿼리에 대해 조건을 만족하는 순서쌍이 적어도 하나 존재함이 보장됩니다. ($0 < G \le L \le 10^{18}$, $L$은 $G$의 배수)

대신, 여러분의 편의를 위해 흐즈로는 $G$와 $L$의 원래 값 대신 $G$와 $L$을 소인수분해한 결과를 제공하기로 했습니다. 모든 쿼리에 충분히 빠르게 대답할 수 있을까요?

첫 번째 줄에 쿼리의 개수 $Q$ ($1 \le Q \le 50\,000$)가 주어집니다.

두 번째 줄부터 $2Q+1$ 번째 줄까지 총 $2Q$개의 줄에 총 $Q$개의 쿼리가 주어집니다. 각 쿼리는 두 줄로 이루어져 있으며, 각 쿼리의 첫 번째 줄에는 $G$를, 두 번째 줄에는 $L$을 소인수분해한 결과가 주어집니다. 소인수분해한 결과는 중복을 허용한 소인수의 개수 $n$과 소인수의 값 $n$개가 공백으로 분리되어 주어집니다. 모든 쿼리에 대해 $0 < G \le L \le 10^{18}$이며 $L$은 $G$의 배수입니다. 입력되는 소인수의 순서는 오름차순이 아닐 수도 있습니다.

입력의 양이 많기 때문에 언어에 따른 빠른 입출력 방법을 사용할 것을 권장합니다. 빠른 입출력 방법은 15552: 빠른 A+B를 참고하세요.

각 쿼리에 대해 각각 한 줄에 문제의 정답을 출력합니다.