33512번 - gcd 놀이

준혁이는 길이가 $N$인 수열 $A$에서 gcd 놀이를 하고 있다. 준혁이는 이 수열의 뒤에 정수 $K$개를 추가하려고 한다.

$K$개의 수를 추가한 수열 $A$의 점수는 다음과 같이 계산한다.

• $\max\limits_{1 \leq i < j \leq N+K}\gcd(A_i,A_j) - \min\limits_{1 \leq i < j \leq N+K}\gcd(A_i,A_j)$

준혁이가 $1$ 이상 $100\,000$ 이하의 임의의 정수 $K$개를 수열의 뒤에 추가했을 때, 가능한 수열의 점수의 최댓값을 구하여라.

첫 줄에 테스트케이스의 수 $T$가 주어진다. $(1 \le T \le 10)$

각 테스트케이스는 두 줄로 이루어져있다.

테스트케이스의 첫째 줄에 수열의 초기 길이 $N$과 추가할 수의 개수 $K$가 공백으로 구분되어 주어진다. $(2 \leq N \leq 10^5;$ $0 \leq K \leq 10^9)$

테스트케이스의 둘째 줄에 수열을 이루는 정수 $A_1$, $A_2$, $\cdots$, $A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_i \leq 10^5)$

각 테스트케이스마다 한 줄에 하나씩 가능한 수열의 점수의 최댓값을 출력한다.

$\gcd(a,b)$는 $a$와 $b$의 최대공약수로 정의된다.