아름다운 분할

시간 제한2초메모리 제한256 MB

요약

배열을 두 개의 비어 있지 않은 부분으로 나누고 두 부분 최대공약수 중 작은 값이 최대가 되도록 한다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 완전 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

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

오늘 컴퓨터 과학 수업에서 선생님이 칠판에 정수 배열을 적었다. 피터는 이 배열의 원소를 두 부분 $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))$ 의 최댓값을 한 줄에 하나씩 출력한다.

예제1

예제 1
입력
```
3
5
3 2 4 6 9
3
3 5 14
4
6 4 6 6
```
예상 출력
```
2
1
4
```