공정한 경고

우리 행성 Jamcode IX에서는 세 번의 Great Events이 일어났다. 그 사건들은 각각 26000, 11000, 6000 슬라보초 전에 일어났다. 지금부터 4000 슬라보초 후에는 그 모든 사건이 일어난 뒤 흐른 시간이 가능한 가장 큰 값인 5000 슬라보초의 배수가 되고... 종말이 찾아올 것이다.

다행히도 여러분은 Jamcode X에 살고 있다! 종말은 Jamcode IX에서 일 년도 채 되지 않은 전에 찾아왔다. 하지만 Jamcode X에는 걱정스러운 예언이 있다. "심판의 순간 이후, N개의 Great Events가 맞는 첫 번째 최적의 기념일에 종말이 찾아올 것이다. 64비트로도 버틸 수 없다. 경고했다."

Jamcode X의 사람들은 이 예언을 매우 걱정하고 있다. 모든 Great Events은 이미 일어났고, 그 시각은 가장 가까운 슬라보초 단위까지 측정되었다. 하지만 최적의 기념일이 언제 찾아올지는 아무도 모른다. Jamcode IX 출신 과학자의 일기를 연구한 뒤, 이 문제를 연구하는 과학자들은 다음과 같은 이론을 세웠다.

심판의 순간은 바로 지금, 여러분이 이 문제를 푸는 순간이다. 지금부터 y ≥ 0 슬라보초 후의 어떤 시점에는 각 Great Events 이후로 흐른 슬라보초의 수가 어떤 최대 수 T로 나누어떨어질 것이다. 가능한 가장 큰 T를 만들어 주는 y의 최솟값을 찾을 수 있다면, 그것이 종말이 찾아올 최적의 기념일을 알려 줄 것이다.

예를 들어 Jamcode IX에는 3번의 Great Events가 있었고, 그것들은 심판의 순간보다 각각 26000, 11000, 6000 슬라보초 전에 일어났다. 4000 슬라보초 후에는 각 사건 이후로 흐른 시간이 T=5000 슬라보초의 배수가 되었고, 종말이 찾아왔다.

여러분의 임무는 종말이 찾아올 때까지 남은 시간을 계산하는 것이다. 하지만 예언을 기억하라. Jamcode X의 사람들이 두 해 동안 문제를 풀어 왔고 64-비트 정수면 언제나 충분했지만, 지금이나 미래에도 언제나 충분하리라는 보장은 없다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ C ≤ 100. 어떤 i, j에 대해 $t_{i}$ ≠ $t_{j}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ N ≤ 3. 1 ≤ $t_{i}$ ≤ $10^{8}$.

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ N ≤ 1000. 1 ≤ $t_{i}$ ≤ $10^{50}$.

입력의 첫 줄에는 테스트 케이스의 수 C가 주어진다. 이어서 C개의 줄이 주어진다. 각 줄은 하나의 정수 N으로 시작하며, 그 뒤에 공백 하나와 공백으로 구분된 N개의 정수 $t_{i}$이 주어진다. 이는 Great Event i가 일어난 뒤 흐른 슬라보초의 수이다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 모든 i에 대해 $t_{i}$ + y가 가능한 가장 큰 정수 인수 T의 배수가 될 때까지 필요한 슬라보초 수의 최솟값이다.

후기

Jamcode 시스템의 사람들에게 다행스럽게도, "종말"은 "거대한 파티"를 잘못 번역한 것으로 밝혀졌다. Jamcode IX에서는 모두가 너무 즐겁게 놀고 있었기 때문에 아무도 이 사실을 전해 주려 하지 않았다.