미리 하는 경고 (라지)

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

당신은 운 좋게도 잼코드 X에 산다. 잼코드 IX의 종말은 채 한 해도 지나지 않은 일이다. 그런데 잼코드 X에도 불길한 예언이 전해진다. "심판의 순간이 지난 뒤, $N$번의 대사건이 맞는 첫 번째 최적 기념일에 종말이 온다. 64비트로는 너를 구할 수 없다. 미리 경고했다."

잼코드 X 사람들은 이 예언을 걱정한다. 대사건은 이미 모두 일어났고 각각의 시각도 슬라보초 단위까지 측정해 두었지만, 최적 기념일이 언제인지는 아무도 모른다. 잼코드 IX 과학자가 남긴 일지를 연구한 끝에 다음 이론이 나왔다.

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

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

종말까지 남은 시간을 구하라. 예언을 잊지 마라. 잼코드 X 사람들이 두 해 동안 문제를 풀며 64비트 정수로 늘 충분했다고 해도, 지금도 앞으로도 충분하다는 보장은 없다.

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

제한

• $1 \le C \le 100$
• $2 \le N \le 1000$
• $1 \le t_i \le 10^{50}$
• $t_i \ne t_j$인 $i$, $j$가 적어도 한 쌍 있다.

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

잼코드 계 주민들에게는 다행스럽게도, "종말"은 "거대한 잔치"를 잘못 옮긴 말로 밝혀졌다. 잼코드 IX의 누구도 이 사실을 알려 주지 않았는데, 잔치가 너무 즐거웠기 때문이다.