공통 생성자 - المسألة

두 정수 $x$와 $y$ ($x, y \ge 2$)에 대하여, $x$를 다음 연산을 0번 이상 수행하여 $y$로 변환할 수 있을 때 $x$를 $y$의 생성자(generator)라고 한다.

예를 들어,

3은 8의 생성자이다. 다음과 같은 연산이 가능하기 때문이다: $3 \xrightarrow{d=3} 6 \xrightarrow{d=2} 8$.
4는 10의 생성자이다. 다음과 같은 연산이 가능하기 때문이다: $4 \xrightarrow{d=4} 8 \xrightarrow{d=2} 10$.
5는 6의 생성자가 아니다. 위 연산을 사용하여 5를 6으로 변환할 수 없기 때문이다.

이제 Kevin이 서로 다른 $n$개의 정수로 이루어진 배열 $a$ ($a_i \ge 2$)를 준다. 모든 $1 \le i \le n$에 대하여 $x$가 $a_i$의 생성자가 되는 정수 $x \ge 2$를 찾거나, 그러한 정수가 존재하지 않음을 판별해야 한다.

각 테스트 케이스는 여러 개의 테스트 케이스를 포함한다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \le t \le 10^4$)가 주어진다. 각 테스트 케이스에 대한 설명이 이어진다.

각 테스트 케이스의 첫 번째 줄에는 배열 $a$의 길이를 나타내는 정수 $n$ ($1 \le n \le 10^5$)이 주어진다.

두 번째 줄에는 배열 $a$의 원소인 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 4 \cdot 10^5$)이 주어진다. 원소들은 서로 다름이 보장된다.

모든 테스트 케이스에 대한 $n$의 합은 $10^5$을 넘지 않는다.

각 테스트 케이스마다 찾은 정수 $x$를 출력한다. 유효한 $x$가 존재하지 않으면 $-1$을 출력한다.

답이 여러 개라면 아무거나 출력해도 된다.

4
3
8 9 10
4
2 3 4 5
2
147 154
5
3 6 8 25 100000

첫 번째 테스트 케이스에서 $x = 2$인 경우:

2는 8의 생성자이다. 다음과 같은 연산이 가능하기 때문이다: $2 \xrightarrow{d=2} 4 \xrightarrow{d=4} 8$.
2는 9의 생성자이다. 다음과 같은 연산이 가능하기 때문이다: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=3} 9$.
2는 10의 생성자이다. 다음과 같은 연산이 가능하기 때문이다: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=2} 8 \xrightarrow{d=2} 10$.

두 번째 테스트 케이스에서는 네 정수의 공통 생성자를 찾는 것이 불가능함이 증명될 수 있다.

QOJ.ac