Command and Conquer: Red Alert 2

Being a nostalgic boy, nocriz loves watching HBK08 and Lantian28 playing the game Command and Conquer: Red Alert 2. However, he doesn't know how to play the game himself.

In the game, you own a sniper initially located at $(-10^{100},-10^{100},-10^{100})$ in a 3D world, and there are $n$ enemy soldiers where the $i$-th soldier is located at $(x_i,y_i,z_i)$. We say the range of the sniper to be $k$, if the sniper can kill all enemies such that $\max(|x_s-x_e|,|y_s-y_e|,|z_s-z_e|) \le k$, where $(x_s,y_s,z_s)$ is the location of the sniper and $(x_e,y_e,z_e)$ is the location of the enemy.

If it is only possible to move the sniper from $(x,y,z)$ to $(x+1,y,z)$, $(x,y+1,z)$ or $(x,y,z+1)$, what is the minimum $k$ such that the sniper can kill all enemies?

The sniper is allowed to move unlimited number of steps, and is allowed to kill enemies whenever he is on an integer coordinate.

The first line contains an integer $t ( 1 \le T \le 50000)$ - the number of test cases. Then $T$ test cases follow.

The first line of each test case contains a single integer $n ( 1\le n \le 5 \times 10^5)$ - the number of enemies.

Then $n$ lines follow, each contains three integers $x_i,y_i,z_i (-10^9 \le x_i,y_i,z_i \le 10^9)$ - the location of the $i$-th enemy.

It is guaranteed that $\sum n \le 2 \times 10^6$.

For each test case, output a single integer representing the answer.

3
2
0 0 0
1 1 1
2
0 1 0
1 0 1
5
1 1 4
5 1 4
1 9 1
9 8 1
0 0 0

0
1
2

2021“MINIEYE杯”中国大学生算法设计超级联赛（6）