공정한 경고 (스몰)

우리 행성 잼코드 IX에서는 세 번의 대사건이 일어났다. 각각 26000, 11000, 6000 슬라보초 전이다. 앞으로 4000 슬라보초가 지나면 세 사건이 일어난 뒤 흐른 시간이 모두 5000 슬라보초의 배수가 된다. 가능한 가장 큰 값이다. 그리고 종말이 온다.

다행히 너는 잼코드 X에 산다. 잼코드 IX의 종말은 아직 1년도 지나지 않았다. 그런데 잼코드 X에도 불길한 예언이 전해진다. "심판의 순간이 지난 뒤, $N$개 대사건의 첫 최적 기념일에 종말이 온다. 64비트로는 너를 구할 수 없다. 경고했다."

잼코드 X 사람들은 이 예언을 몹시 걱정한다. 대사건은 모두 이미 일어났고 그 시각도 슬라보초 단위로 측정했지만, 최적 기념일이 언제인지는 아무도 모른다. 잼코드 IX 과학자의 일기를 연구한 학자들이 다음 이론을 내놓았다.

심판의 순간은 바로 지금, 이 문제를 푸는 순간이다. 지금부터 $y \ge 0$ 슬라보초가 지난 어느 시점에, 각 대사건 이후 흐른 시간이 모두 어떤 최대의 수 $T$로 나누어떨어진다. 이 가장 큰 $T$를 만드는 가장 작은 $y$가 종말이 오는 최적 기념일이다.

예를 들어 잼코드 IX에는 대사건이 3개 있었고, 심판의 순간보다 각각 26000, 11000, 6000 슬라보초 전에 일어났다. 4000 슬라보초 뒤에 각 사건 이후 흐른 시간이 모두 $T = 5000$의 배수가 되었고, 종말이 왔다.

종말까지 남은 시간을 구하라. 다만 예언을 기억하라. 잼코드 X 사람들이 2년 동안 문제를 풀며 64비트 정수로 늘 충분했지만, 이번에는 충분하지 않다.

첫 줄에 테스트 케이스의 수 $C$가 주어진다. 이어서 $C$개의 줄이 주어진다. 각 줄은 정수 $N$으로 시작하고, 공백 한 칸 뒤에 $N$개의 정수 $t_i$가 공백으로 구분되어 주어진다. $t_i$는 $i$번째 대사건이 일어난 뒤 흐른 슬라보초 수이다.

제한

• $1 \le C \le 100$
• $2 \le N \le 3$
• $1 \le t_i \le 10^{50}$
• 어떤 $i$, $j$에 대해 $t_i \ne t_j$이다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 $i$에 대해 $t_i + y$가 가능한 가장 큰 정수 인수 $T$의 배수가 되게 하는 최소의 슬라보초 수이다.

잼코드 항성계 주민들에게는 다행히도, "종말"은 "거대한 파티"의 오역이었다. 잼코드 IX 사람들은 노느라 너무 바빠서 아무도 이 사실을 알려주지 않았다.