커맨드 앤 컨커: 레드 얼럿 2

낡은 게임을 좋아하는 Nocriz는 HBK08과 Lantian28이 Command and Conquer: Red Alert 2를 하는 모습을 보는 것을 즐깁니다. 하지만 그는 직접 게임하는 법을 모릅니다.

이 게임에서 당신은 3차원 세계에 있는 저격수 한 명을 가지고 있습니다. 저격수는 처음에 $(-10^{100}, -10^{100}, -10^{100})$ 위치에 있습니다. 적 병사는 $n$명이고, $i$번째 병사는 $(x_i, y_i, z_i)$ 위치에 있습니다. 저격수의 위치를 $(x_s, y_s, z_s)$, 적의 위치를 $(x_e, y_e, z_e)$라고 할 때, 모든 적에 대해 $\max(|x_s - x_e|, |y_s - y_e|, |z_s - z_e|) \le k$가 성립하면 저격수의 사거리가 $k$이고 모든 적을 처치할 수 있다고 합니다.

한 번의 이동에서 저격수는 $(x, y, z)$에서 $(x + 1, y, z)$, $(x, y + 1, z)$, $(x, y, z + 1)$ 중 한 곳으로 움직일 수 있습니다. 적은 움직이지 않습니다. 저격수는 이동을 무한히 여러 번 할 수 있고, 좌표가 모두 정수일 때마다 사거리 안에 있는 적을 처치할 수 있습니다. 저격수가 결국 모든 적을 처치할 수 있는 최소 사거리 $k$는 얼마입니까?

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 5 \cdot 10^4$)가 주어집니다. 이어서 $T$개의 테스트 케이스가 주어집니다.

각 테스트 케이스의 첫 줄에는 적의 수 $n$ ($1 \le n \le 5 \cdot 10^5$)이 주어집니다.

이어서 $n$개의 줄이 주어지며, 각 줄에는 $i$번째 적의 위치를 나타내는 정수 $x_i, y_i, z_i$ ($-10^9 \le x_i, y_i, z_i \le 10^9$)가 주어집니다.

모든 테스트 케이스의 $n$을 합하면 $2 \cdot 10^6$을 넘지 않습니다.

각 테스트 케이스마다 최소 사거리 $k$를 한 줄에 정수로 출력합니다.