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$의 최대공약수로 정의된다.