두 정육면체

"별들을 봐요, 당신을 위해 얼마나 빛나는지 봐요." - Coldplay, "Yellow"

아주 먼 은하에 많은 별이 있다. 각 별은 특정한 위치(삼차원 공간)와 반지름을 갖는 구이다. 별들은 서로 겹칠 수도 있다.

별들이 너무나 아름다워서 그 모습을 영원히 간직하고 싶다! 정수인 동일한 모서리 길이를 갖는 두 정육면체를 만들어 공간에 배치하되, 각 별을 완전히 포함하는 정육면체가 적어도 하나는 있도록 하려고 한다. (별이 두 정육면체의 합집합에 완전히 포함되는 것만으로는 충분하지 않다.) 별 위의 어떤 점도 정육면체 밖에 있지 않을 때, 그리고 그럴 때에만 별이 정육면체에 완전히 포함된다고 한다. 정육면체의 면 위에 정확히 놓인 점도 여전히 정육면체 내부에 있는 것으로 간주한다.

정육면체들은 공간의 어디에나 배치할 수 있지만, 모서리가 좌표축과 평행하도록 배치해야 한다. 정육면체가 별이나 서로와 겹쳐도 된다.

이 목표를 달성할 수 있게 하는 최소 정수 모서리 길이는 얼마인가?

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 20초. 메모리 제한: 1GB. -$10^{8}$ ≤ $X_{i}$ ≤ $10^{8}$, 모든 i에 대해. -$10^{8}$ ≤ $Y_{i}$ ≤ $10^{8}$, 모든 i에 대해. -$10^{8}$ ≤ $Z_{i}$ ≤ $10^{8}$, 모든 i에 대해. 1 ≤ $R_{i}$ ≤ $10^{8}$, 모든 i에 대해.

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

2 ≤ N ≤ 16.

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

2 ≤ N ≤ 2000.

입력은 테스트 케이스의 수인 정확히 하나의 정수 T가 포함된 한 줄로 시작한다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 별의 수를 나타내는 정수 N이 포함된 한 줄로 시작한다.

그다음 N개의 줄이 주어진다. i번째 줄에는 공백으로 구분된 정수 4개인 $X_{i}$, $Y_{i}$, $Z_{i}$와 $R_{i}$이 주어지며, $i^{th}$번째 별의 중심에 대한 (X, Y, Z) 좌표와 $i^{th}$번째 별의 반지름을 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며 (1부터 시작), y은 위에서 설명한 문제를 해결하는 정육면체의 최소 모서리 길이이다.

첫 번째 테스트 케이스에서 한 가지 해법은 모서리 길이가 3인 두 정육면체를, (x, y, z) 좌표가 최소인 꼭짓점이 각각 (0, 0, 0)와 (3, 3, 3)에 있도록 배치하는 것이다. 두 번째 테스트 케이스에서 한 가지 해법은 모서리 길이가 5인 두 정육면체를, (x, y, z) 좌표가 최소인 꼭짓점이 각각 (-1, -1, -1)와 (1, 2, 3)에 있도록 배치하는 것이다.