아름다운 분할

피터는 오늘 정수 집합의 최대공약수를 배웠다. 이 개념이 마음에 쏙 들어서 이제는 무엇을 보든 최대공약수를 찾으려 한다.

오늘 컴퓨터 과학 수업에서 선생님이 칠판에 정수 배열을 적었다. 피터는 이 배열의 원소를 두 부분 $M_1$과 $M_2$로 나누면 $\gcd(M_1)$과 $\gcd(M_2)$가 둘 다 꽤 커진다는 사실을 알아차렸다. 여기서 $\gcd(M)$은 $M$에 속한 모든 수의 최대공약수다.

피터는 이 문제를 일반화하기로 했다. 배열이 주어지면 모든 원소를 비어 있지 않은 두 부분 $M_1$과 $M_2$로 나눈다. 원소 하나는 정확히 한 부분에만 들어간다. $\min(\gcd(M_1), \gcd(M_2))$가 최대가 되도록 나누고, 그 최댓값을 출력한다.

입력은 여러 개의 테스트로 이루어진다. 첫째 줄에 테스트의 개수 $t$가 주어진다 ($1 \le t \le 1000$).

각 테스트는 두 줄로 주어진다. 첫째 줄에는 배열의 크기 $n$이 주어진다 ($2 \le n \le 5 \times 10^4$). 둘째 줄에는 배열의 원소 $a_i$가 $n$개 주어진다 ($1 \le a_i \le 10^9$).

한 입력에 들어 있는 모든 테스트의 $n$을 더한 값은 $5 \times 10^4$을 넘지 않는다.

각 테스트마다 $\min(\gcd(M_1), \gcd(M_2))$의 최댓값을 한 줄에 하나씩 출력한다.